An Exact Algorithm for IP Column Generation

François Vanderbeck and Laurence Wolsey ()
Additional contact information
François Vanderbeck: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Laurence Wolsey: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1994019, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: An exact column generation algorithm for integer programs with a large (implicit) number of columns is presented. The family of problems that can be treated includes not only standard partitioning problems such as bin packing and certain vehicle routing problems in which the columns generated have 0 - 1 components and a right hand side vector of 1 's, but also the cutting stock problem in which the columns and right hand side are nonnegative integer vectors. We develop a combined branching and subproblem modification scheme that generalizes existing approaches, and also describe the use of lower bounds to reduce tailing-off effects.

Date: 1994-04-01
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1994.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1994019

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().