Abstract | ||
---|---|---|
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. © 2004 Wiley Periodicals, Inc. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1002/net.v43:4 | Networks |
Keywords | Field | DocType |
multileaf collimators,network model,column generation formulation,nonlinear mixed-integer programming formulation,shortest path problem,beam-on time,cancer radiation therapy,side-constrained network flow formulation,treatment time,polynomial time,mlc equipment,cancer radiation treatment,integer programming,multileaf collimator | Flow network,Column generation,Mathematical optimization,Shortest path problem,Matrix (mathematics),Integer programming,Linear programming,Integer matrix,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 4 | 0028-3045 |
Citations | PageRank | References |
42 | 6.79 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Natashia Boland | 1 | 726 | 67.11 |
Horst W. Hamacher | 2 | 562 | 57.39 |
Frank Lenzen | 3 | 157 | 16.85 |