VANDERBECK, François

Métadonnées

Licence d’utilisation du document

VANDERBECK, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]

Langue

Communication dans un congrès

Ce document a été publié dans

EURO INFORMS 26, 2013-07-01, Rome. 2013-07-03

Résumé en anglais

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.< Réduire

Mots clés en anglais

Extended formulations

Column Generation

Métadonnées

Partager cette publication !

Licence d’utilisation du document

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

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

Origine

Unités de recherche