Mixed Integer Programming Approaches to Treatment Planning for Brachytherapy – Application to Permanent Prostate Implants

Mixed integer programming models and computational strategies developed for treatment planning optimization in brachytherapy are described. The problem involves the designation of optimal placement of radioactive sources (seeds) inside a tumor site. Two MIP models are described. The resulting MIP instances are difficult to solve, due in large part to dense constraint matrices with large disparities in the magnitudes of the nonzero entries. A matrix reduction and approximation scheme is presented as a computational strategy for dealing with the dense matrices. Penalty-based primal heuristic and branching strategies to assist in the solution process are also described. Numerical results are presented for 20 MIP instances associated with prostate cancer cases. Compared to currently used computer-aided planning methods, plans derived via the MIP approach use fewer seeds (20–30 fewer) and needles, and provide better coverage and conformity – measures commonly used to assess the quality of treatment plans. Good treatment plans are returned in 15 CPU minutes, suggesting that incorporation of this MIP-based optimization module into a real-time comprehensive treatment planning system is feasible.