An exact algorithm for IP column generation

An exact algorithm for IP column generation

0.00 Avg rating0 Votes
Article ID: iaor1998397
Country: Netherlands
Volume: 19
Issue: 4
Start Page Number: 151
End Page Number: 159
Publication Date: Oct 1996
Journal: Operations Research Letters
Authors: ,
Keywords: bin packing
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.

Reviews

Required fields are marked *. Your email address will not be published.