Minimizing beam-on time in cancer radiation treatment using multileaf collimators

In this article the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators (MLC) is investigated. It is shown that the problem is equivalent to decomposing a given integer matrix into a positive linear combination of (0, 1) matrices. These matrices, called shape matrices, must have the strict consecutive-1-property, together with another property derived from the technological restrictions of the MLC equipment. Various decompositions can be evaluated by their beam-on time (time during which radiation is applied to the patient) or the treatment time (beam-on time plus time for setups). We focus on the former, and develop a nonlinear mixed-integer programming formulation of the problem. This formulation can be decomposed to yield a column generation formulation: a linear program with a large number of variables that can be priced by solving a subproblem. We then develop a network model in which paths in the network correspond to feasible shape matrices. As a consequence, we deduce that the column generation subproblem can be solved as a shortest path problem. Furthermore, we are able to develop two alternative models of the problem as side-constrained network flow formulations, and so obtain our main theoretical result that the problem is solvable in polynomial time. Finally, a numerical comparison of our exact solutions with those of well-known heuristic methods shows that the beam-on time can be reduced by a considerable margin. (C) 2004 Wiley Periodicals, Inc.