Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas
Contributor : François Vanderbeck <>
Submitted on : Tuesday, July 16, 2013 - 6:08:52 PM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM


  • HAL Id : hal-00845318, version 1



François Vanderbeck. Extended formulations, Column Generation, and stabilization: synergies in the benefit of large scale applications. EURO INFORMS 26, EURO INFORMS, Jul 2013, Rome, Italy. ⟨hal-00845318⟩



Record views