On Compact Formulations for Integer Programs Solved by Column Generation

Daniel Villeneuve (DanielVad-opt.com)
Jacques Desrosiers (Jacques.Desrosiershec.ca)
Marco Luebbecke (M.Luebbeckemath.tu-berlin.de)
Francois Soumis (Francois.Soumisgerad.ca)

Abstract: Column generation has become a powerful tool in solving large scale integer programs. We argue that most of the often reported compatibility issues between pricing oracle and branching rules disappear when branching decisions are based on the reduction of the variables of the oracle's domain. This can be generalized to branching on variables of a so-called compact formulation. We constructively show that such a formulation always exists under mild assumptions. It has a block diagonal structure with identical subproblems. Our proposal opens the way for the development of branching rules adapted to the oracle structure and the coupling constraints.

Keywords: Integer programming; column generation; branch-and-bound

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Oper. Res. 53(6):1007-1023, 2005. DOI: 10.1287/opre.1050.0234

Download: [Postscript][PDF]

Entry Submitted: 02/03/2003
Entry Accepted: 02/03/2003
Entry Last Modified: 11/27/2007

Modify/Update this entry