2 — 15:30 — Some Applications of Benders Decomposition to Location and Network Design Problems
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 onto the space of the complicating variables, and by using a cutting plane method where cuts are generated by solving the subproblem. Since 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 two decades, one has witnessed a renewed interest in Benders decomposition with the introduction of several novel ideas that improve performance. The purpose of this talk is to give an overview of the main acceleration techniques by focusing on two families of problems where Benders decomposition has proven especially effective: facility location problems and network design problems. After briefly explaining the general methodology and the main practical enhancements, we will present examples of successful applications to set covering, hub location, and fixed-charge network design problems. In each case, we will focus on strategies for the efficient generation of strong cuts.