Optimization Online


Column Generation for Extended Formulations

Ruslan Sadykov(ruslan.sadykov***at***inria.fr)
Francois Vanderbeck(fv***at***math.u-bordeaux1.fr)

Abstract: Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools and derive valid inequalities for the original formulation, or consider an approximate extended formulation (f.i., by aggregating variables). Both approaches result in outer approximations of the intended extended formulation. An alternative is to work with inner approximations defined and improved by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which the original problem extended formulation is derived. Then, one can implement column generation for this extended formulation by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. Such ``column-and-row generation'' procedure is reviewed and analysed herein. We compare numerically a direct handling of the extended formulation, a standard column generation approach, and the ``column-and-row generation'' procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.

Keywords: Extended formulations for MIP, Column-and-Row Generation, Stabilization.

Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 07/08/2011
Entry Accepted: 07/08/2011
Entry Last Modified: 07/08/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society