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.
Type de document :
Article dans une revue
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〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00661758
Contributeur : François Vanderbeck <>
Soumis le : mercredi 20 février 2013 - 15:38:37
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : dimanche 2 avril 2017 - 02:55:06

Fichier

cgefHall.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

676

Téléchargements de fichiers

412