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.