Skip to Main content Skip to Navigation
New interface
Journal articles

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 tighter reformu- lations 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 work with inner approximations defined and improved by generating dynamically vari- ables and constraints. When the extended formulation stems from subproblems' reformulations, one can implement column generation for the extended formulation using a Dantzig-Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current re- stricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions. This so-called "column-and-row gen- eration" procedure is revisited here in a unifying presentation that generalizes the column generation algorithm and extends to the case of working with an approximate extended formulation. The interest of the approach is evaluated numerically on ma- chine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the "column-and-row generation" procedure, high- lighting 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.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : François Vanderbeck Connect in order to contact the contributor
Submitted on : Wednesday, February 20, 2013 - 3:38:37 PM
Last modification on : Saturday, June 25, 2022 - 7:44:20 PM
Long-term archiving on: : Sunday, April 2, 2017 - 2:55:06 AM


Files produced by the author(s)




Ruslan Sadykov, François Vanderbeck. Column Generation for Extended Formulations. EURO Journal on Computational Optimization, 2013, 1 (1-2), pp.81-115. ⟨10.1007/s13675-013-0009-9⟩. ⟨hal-00661758v2⟩



Record views


Files downloads