An exact algorithm for IP column generation

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.