Benders’ decomposition

Classical Benders’ algorithm has been applied to many areas including network design, integrated aircraft routing and crew scheduling, and production management. Originally conceived by J. F. Benders in 1962, Benders’ decomposition is a technique designed to exploit the structure of large linear or mixed-integer optimization problems. Classical Benders’ decomposition is often used on problems with many continuous variables, lending itself well to SDIO, as one of the challenges of SDIO is the enormous number of continuous variables, each associated with the duration of a potential shot. However, the literature on Benders’ algorithm in radiation therapy treatment planning is sparse. The only such previous studies apply classical and subsequently combinatorial Benders’ decomposition algorithms in radiation therapy were in the context of the integral uence map decomposition problem with rectangular apertures (IFR) in intensity modulated radiation therapy; however, SDIO is quite different from IFR because of the smaller problem size, rectangular apertures and lack of continuous variables in the objective function found in IFR.
One notable development to classical Benders’ decomposition is the use of local branching on potential solutions by exploring the neighborhood of any solution using local branching at each Benders’ iteration, generating many incumbent solutions (and optimality cuts). This strategy diers from the classical Benders’ algorithms found in this thesis as it performs additional work at each Benders’ iteration to nd promising feasible solutions in the neighboorhood of the current solution instead of locating feasible solutions in a Phase I step. It is possible to incorporate local branching into our twophase classical algorithm, as well as our combinatorial algorithm, although this strategy has not been attempted in this thesis.
Unforunately, one weakness of classical Benders’ decomposition is that it requires all subproblem variables to be continuous, and the subproblem objective and constraints to be linear so that the subproblem is a linear program, and linear programming duality theory can be used to develop valid cuts. To deal with this limitation, logic-based Benders’ decomposition was developed as a generalization of classical Benders’ decomposition.
Logic-based Benders’ is similar to classical Benders in that it decomposes a large-scale optimization problem into a master problem and one or many subproblems,

and uses constraint generation to gradually decrease the solution space of the master problem. However, instead of using a linear programming dual to generate cuts, Logicbased Benders’ decomposition uses the broader concept of an inference dual, which can be dened as an optimization problem that nds the best possible bound implied by a set of master problem variables, also called primary variables. This best possible bound is used to generate cuts that are passed back to the master problem. Logic-based Benders’ decomposition has been applied frequently in the past to various dicult planning and scheduling problems. However, logic-based Benders’ decomposition has been used in the operating rooms planning and scheduling eld only in.