Extended formulations, Column Generation, and stabilization: synergies in the benefit of large scale applications

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 : Extended formulations entail working in an extended variable space which typically results in a tighter formulation for mixed integer programs. The Dantzig-Wolfe decomposition paradigm and the resulting column generation reformulation is a special case where one expresses global solutions as a combination of solutions to identified subproblems. Extended formulations present the advantage of being amenable to a direct handling by a MIP solver and a rich variable space in which to express cuts or branching constraints; but their size blows rapidly too large for practical purposes. Column generation reformulation on the other hand requires a branch-and-price solver based on a specific oracle for the subproblems and efficient stabilization strategies to accelerate convergence. The combination of these two paradigms offers a truly practical approach to well-structured applications, where formulation size is handled dynamically, stabilization is less of an issue thanks to natural recombinations of subproblem solutions, and inherent stage-by-stage approximation strategies provide primal heuristic solutions. Our presentation aims to review the pros of an extended formulation approach in combination with column generation and to highlight practical issues. The performance of such approach shall be illustrated on academic models and realistic size industrial applications.
Type de document :
Communication dans un congrès
EURO INFORMS 26, Jul 2013, Rome, Italy. 2013, 〈http://www.math.u-bordeaux.fr/~fv/papers/presCgEfEuro2013.pdf〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00845318
Contributeur : François Vanderbeck <>
Soumis le : mardi 16 juillet 2013 - 18:08:52
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

  • HAL Id : hal-00845318, version 1

Collections

Citation

François Vanderbeck. Extended formulations, Column Generation, and stabilization: synergies in the benefit of large scale applications. EURO INFORMS 26, Jul 2013, Rome, Italy. 2013, 〈http://www.math.u-bordeaux.fr/~fv/papers/presCgEfEuro2013.pdf〉. 〈hal-00845318〉

Partager

Métriques

Consultations de la notice

359