Benders’ algorithm applied to the sector duration and isocenter optimization problem
We describe two different Benders’-type algorithms to effciently solve SDIO. We start by showing that SDIO can be decomposed into an integer master problem and a linear subproblem. Once decomposed, we solve SDIO using a classical two-stage Benders’ algorithm, and show that the two-stage Benders’ algorithm is an effcient method to solve this problem. We test this two-stage Benders’ approach on seven different clinical cases, and show that it nds acceptable clinical plans, that it outperforms a standard one-stage Benders’ algorithm, and that it is capable of solving larger problems than commercial branch-and-cut solvers. We also propose and implement a combinatorial Benders’ algorithm, and show that the combinatorial Benders’ algorithm is faster than the classical Benders’ algorithm when it is able to run, but is not able to even begin the solution process for the larger test cases because of large overhead times.
As mentioned before, SDIO combines the isocenter location stage and the sector duration optimization stage of a typical two-stage radiation therapy inverse planning algorithm into a single mixed integer optimization problem. Instead of using a traditional branch-and-cut algorithm, we implement Benders’-type approaches designed for large-scale optimization problems.
Classical Benders’ algorithm uses a decomposition that divides the mixed-integer linear program into one or many subproblems with only continuous variables, and a master problem with an exponential number of constraints, each corresponding to an extreme point or an extreme ray of the dual of the subproblem. Although there are an exponential number of potential master problem constraints, a Benders’ algorithm is used, expecting that an optimal solution can be found with only a subset of the complete set of constraints. Our classical Benders’ decomposition implementation has two signicant dierences from a standard implementation. Firstly, the solver that is used to solve the Benders’ linear programming subproblems use an interior-point method with the previous subproblems’ solution as a starting point. As each subproblem is only slightly dierent than the previous one, using the previous subproblem’s starting point has been shown to accelerate the subproblem solution process. Secondly, we use a twophase technique to accelerate the solution process. In Phase I, we simply solve the linear relaxation of SDIO using Benders’ decomposition. With each iteration of our Phase I, we use a rounding heuristic to nd an incumbent solution to the original SDIO problem, and generate cuts to use in Phase II. The optimal solution to Phase I is also used as a lower bound to start Phase II. Using these techniques to accelerate our Benders’ decomposition implementation, we are able to eciently solve SDIO.
A second algorithm that was implemented incorporates combinatorial Benders’ cuts into the classical Benders’ algorithm. Our implementation can be seen as a hybrid between the combinatorial benders’ algorithm developed in and a classical Benders’approach. In, the authors formulate a special kind of logic based no-good cut derived from a feasibility subproblem, this cut can be called a combinatorial constraint. In practice, we cannot simply adopt a pure combinatorial Benders’ decomposition as both the master problem and the subproblem of our decomposition have a non-zero objective function. As a result, we create a hybrid algorithm that uses no-good style cuts when the master problem is found to be infeasible, but that reverts to classical Benders’ cuts otherwise.
