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.
Liste complète des métadonnées

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-00661758
Contributor : François Vanderbeck <>
Submitted on : Wednesday, February 20, 2013 - 3:38:37 PM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM
Document(s) archivé(s) le : Sunday, April 2, 2017 - 2:55:06 AM

File

cgefHall.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

838

Files downloads

488