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; th at can be treated includes not only standard partitioning problems suc h as bin packing and certain vehicle routing problems in which the col umns 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-ha nd side are nonnegative integer vectors. We develop a combined branchi ng and subproblem modification scheme that generalizes existing approa ches, and also describe the use of lower bounds to reduce tailing-off effects.