Skip to Main content Skip to Navigation
Conference papers

Column Generation for Extended Formulations

Ruslan Sadykov 1, 2 François Vanderbeck 1, 2
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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 to derive valid inequalities for the original formulation and implement a cutting plane approach. Or, one can approximate the reformulation, using techniques such as variable aggregation or reformulation of a submodel only. These approaches result in working with an outer approximation of the intended extended formulation. The alternative considered here is an inner approximation obtained 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 an extended formulation for the global problem can be derived. Then, one can implement column generation for the extended formulation mimicking that 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. The paper reviews the applications of such ``column-and-row generation'' procedure from the literature and analyses this approach's potential benefits compared to a standard column generation approach. Numerical experiments highlight a key observation: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.
Document type :
Conference papers
Complete list of metadatas
Contributor : Ruslan Sadykov <>
Submitted on : Thursday, November 25, 2010 - 1:56:39 PM
Last modification on : Monday, November 25, 2019 - 11:26:13 AM

Links full text




Ruslan Sadykov, François Vanderbeck. Column Generation for Extended Formulations. 6th Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. pp.357-362, ⟨10.1016/j.endm.2011.05.061⟩. ⟨inria-00539870⟩



Record views