Mixed integer programming approaches to exact minimization of total treatment time in cancer radiotherapy using multileaf collimators

The effectiveness of radiation therapy for cancer depends on the patient remaining still during treatment. It is thus important to minimize the total treatment time (TTT). When such treatment is delivered using multileaf collimators in “step-and-shoot” mode, it consists of a sequence of collimator configurations, or patterns; for each, the patient is exposed to radiation for a specified time, or beam-on time. The TTT can thus be divided into the total beam-on time and the time spent reconfiguring the collimators. The latter can reasonably be approximated by the number of patterns, multiplied by a constant overhead time per pattern. Previous approaches to this problem have all been heuristic; in particular none of them actually use the pattern overhead time to ascertain the best trade-off between beam-on time and number of patterns. In this paper, we develop exact solution approaches, based on mixed integer programming (MIP) formulations, which minimize the TTT. We consider direct solution of MIP formulations, and then exploit the bicriteria structure of the objective to derive an algorithm that “steps up” through the number of patterns used, leading to substantial computational savings.