Benders decomposition and an IP-based heuristic for selecting IMRT treatment beam angles

• We apply two Bender decomposition algorithms for intensity modulated radiation therapy treatment planning.
• We develop a novel two-stage heuristic for intensity modulated radiation therapy treatment planning.
• All methods are tested using real patient data to evaluate their effectiveness.
• Best results were provided by our two-stage heuristic with local branching.

In this paper, two Benders decomposition algorithms and a novel two-stage integer programming-based heuristic are presented to optimize the beam angle and fluence map in Intensity Modulated Radiation Therapy (IMRT) planning. Benders decomposition is first implemented in the traditional manner by iteratively solving the restricted master problem and then identifying and adding the violated Benders cuts. We also implemented Benders decomposition using the “lazy constraint” feature included in CPLEX. In contrast, the two-stage heuristic first seeks to find a good solution by iteratively eliminating the least used angles in the linear programming relaxation solution until the size of the formulation is manageable. In the second stage of the heuristic, the solution is improved by applying local branching. The various methods were tested on real patient data to evaluate their effectiveness and runtime characteristics. The results indicated that implementing Benders using the lazy constraint usually led to better feasible solutions than the traditional approach. Moreover, the LP rounding heuristic was seen to generate high-quality solutions within a short amount of time, with further improvement obtained with the local branching search.