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.
Type de document :
Communication dans un congrès
6th Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. Elsvier, 37, pp.357-362, 2011, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2011.05.061〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00539870
Contributeur : Ruslan Sadykov <>
Soumis le : jeudi 25 novembre 2010 - 13:56:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

Collections

Citation

Ruslan Sadykov, François Vanderbeck. Column Generation for Extended Formulations. 6th Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. Elsvier, 37, pp.357-362, 2011, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2011.05.061〉. 〈inria-00539870〉

Partager

Métriques

Consultations de la notice

213