François Vanderbeck (Department of Applied Mathematics, University of Bordeaux 1)

Synergies between extended formulation and column generation approaches
Friday 6 December 2013 at 13.00, JCMB 6206

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.

Seminars by year

Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996