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

Date

2014-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

To optimize the beam angle and fluence map in Intensity Modulated Radiation Therapy (IMRT) planning, we apply Benders decomposition as well as develop a two-stage integer programming-based heuristic. Benders decomposition is first implemented in the traditional manner by iteratively solving the restricted master problem, and then identifying and adding the violated Benders cut. We also implemented Benders decomposition using the “lazy constraint” feature included in CPLEX. In contrast, our 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 in order to investigate 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.

Description

text

Citation