An exact algorithm for IP column generation
(1996) Operations Research Letters — Vol. 19, n° 4, p. 151-159 (1996)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 642.32 KB
Details
- Authors
- 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.
- Affiliations
Citations
Vanderbeck, F., & Wolsey, L. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19(4), 151-159. https://doi.org/10.1016/0167-6377(96)00033-8 (Original work published 1996)