Optimization Days 2017

HEC Montréal, May 8-10, 2017

1st Canadian Healthcare Optimization Workshop (CHOW)

HEC Montréal, May 10-11, 2017



HEC Montréal, 8 — 11 May 2017

Schedule Authors My Schedule

MB1 Exposé magistral 1 / Tutorial 1

May 8, 2017 10:30 AM – 12:10 PM

Location: Banque CIBC

Chaired by Monia Rekik

1 Presentation

  • 10:30 AM - 12:10 PM

    ANNULERecent (and not so recent) advances in Benders decomposition

    • Jean-François Cordeau, presenter, HEC Montréal, GERAD, CIRRELT

    Benders decomposition is a mathematical decomposition technique designed to solve large-scale linear and mixed-integer programs comprising two sets of variables such that a more tractable subproblem is obtained when the values of some "complicating" variables are fixed. The technique works by projecting the original problem on the space of the complicating variables, and by using a cutting plane method where cuts are generated by solving the subproblem. In the 55 years following its introduction by Jacques F. Benders in 1962, the approach has been applied successfully to a wide variety of problems arising, among others, in supply chain management, transportation, telecommunications, and energy management. Despite its success, however, it has long remained less well known than dual decomposition methods such as Lagrangian relaxation and Dantzig-Wolfe decomposition. Over the last decade, one has witnessed a renewed interest in Benders decomposition with the introduction of several novel ideas that improve performance. The purpose of this tutorial is to introduce the basic Benders decomposition methodology, to present several acceleration techniques, and to survey recent advances. Applications to network design problems will also be discussed.