|
Matteo Fischetti:
Modern Benders
Abstract:
Benders' decomposition is one of the most famous tools for Mathematical Programming, and is the method of choice, e.g., in mixed-integer stochastic programming. Its hallmark is the capability of decomposing certain types of linear models into smaller subproblems, each of which can be solved individually to produce local information (notably, cutting planes) to be exploited by a centralized "master" problem. In this talk, we will first present a simple derivation of Benders' theory for general convex problems. We will then show how to embed the Benders approach within a modern branch-and-cut mixed-integer programming solver, addressing explicitly all the ingredients that are instrumental for its success. Some computational experiences will be briefly discussed.
|