zbMATH — the first resource for mathematics

A shortest path-based approach to the multileaf collimator sequencing problem. (English) Zbl 1235.90125
Summary: The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.

90C27 Combinatorial optimization
Full Text: DOI
[1] Agazaryan, N.; Solberg, T.D., Segmental and dynamic intensity-modulated radiotherapy delivery techniques for micro-multileaf collimator, Medical physics, 30, 7, 1758-1767, (2003)
[2] Ahuja, R.K.; Hamacher, H.W., A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapy, Networks, 45, 1, 36-41, (2005) · Zbl 1061.92033
[3] D. Baatar, N. Boland, S. Brand, P. Stuckey, Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches, in: CPAIOR, 2007, pp. 1-15. · Zbl 1214.15021
[4] Baatar, D.; Hamacher, H.; Ehrgott, M.; Woeginger, G., Decomposition of integer matrices and multileaf collimator sequencing, Discrete applied mathematics, 152, 1-3, 6-34, (2005) · Zbl 1084.15014
[5] Bahr, G.; Kereiakes, J.; Horwitz, H.; Finney, R.; Galvin, J.; Goode, K., The method of linear programming applied to radiation therapy planning, Radiology, 91, 686-693, (1968)
[6] Bansal, N.; Coppersmith, D.; Schieber, B., Minimizing setup and beam-on times in radiation therapy, (), 27-38 · Zbl 1155.92325
[7] Ben Amor, H.M.T.; Desrosiers, J.; Frangioni, A., On the choice of explicit stabilizing terms in column generation, Discrete applied mathematics, 157, 6, 1167-1184, (2009) · Zbl 1169.90395
[8] Boland, N.; Hamacher, H.W.; Lenzen, F., Minimizing beam-on time in cancer radiation treatment using multileaf collimators, Networks, 43, 4, 226-240, (2004) · Zbl 1044.92030
[9] Bortfeld, T.R.; Kahler, D.L.; Waldron, T.J.; Boyer, A.L., X-ray field compensation with multileaf collimators, International journal of radiation oncology biology physics, 28, 3, 723-730, (1994)
[10] Brand, S., The sum-of-increments constraint in the consecutive-ones matrix decomposition problem, (), 1417-1418
[11] R.E. Burkard, Open problem session, in: Oberwolfach Conference on Combinatorial Optimization, 2002.
[12] Cambazard, H.; O’Mahony, E.; O’Sullivan, B., A shortest path-based approach to the multileaf collimator sequencing problem, (), 41-55
[13] H. Cambazard, E. O’Mahony, B. O’Sullivan, Hybrid methods for the multileaf collimator sequencing problem, in: CPAIOR, 2010, pp. 56-70. · Zbl 1285.68152
[14] Collins, M.J.; Kempe, D.; Saia, J.; Young, M., Nonnegative integral subset representations of integer sets, Information processing letters, 101, 3, 129-133, (2007) · Zbl 1185.68854
[15] Dai, J.; Zhu, Y., Minimizing the number of segments in a delivery sequence for intensity-modulated radiation therapy with a multileaf collimator, Physics in medicine and biology, 28, 1, 2113-2120, (2001)
[16] Dantzig, G.B.; Wolfe, P., Decomposition principle for linear programs, Operations research, 8, 101-111, (1960) · Zbl 0093.32806
[17] de Azevedo Pribitkin, W., Simple upper bounds for partition functions, The Ramanujan journal, 18, 113-119, (2009), URL: http://dx.doi.org/10.1007/s11139-007-9022-z · Zbl 1195.11138
[18] Demassey, S.; Pesant, G.; Rousseau, L.-M., A cost-regular based hybrid column generation approach, Constraints, 11, 4, 315-333, (2006) · Zbl 1117.90066
[19] Desaulniers, G.; Desrosiers, J.; Solomon, M.M., Column generation, (2005), Springer · Zbl 1084.90002
[20] du Merle, O.; Villeneuve, D.; Desrosiers, J.; Hansen, P., Stabilized column generation, Discrete mathematics, 194, 1-3, 229-237, (1999) · Zbl 0949.90063
[21] Ehrgott, M.; Güler, Çigdem; Hamacher, H.W.; Shao, L., Mathematical optimization in intensity modulated radiation therapy, 4or, 6, 3, 199-262, (2008) · Zbl 1168.90019
[22] Engel, K., A new algorithm for optimal multileaf collimator field segmentation, Discrete applied mathematics, 152, 1-3, 35-51, (2005) · Zbl 1076.92026
[23] C. Engelbeen, The segmentation problem in radiation therapy, Ph.D. Thesis, Université Libre de Bruxelles, Département de Mathématique, Bruxelles, 2010. · Zbl 1277.90162
[24] Engelbeen, C.; Fiorini, S., Constrained decompositions of integer matrices and their applications to intensity modulated radiation therapy, Networks, 55, 2, 138-148, (2010) · Zbl 1201.15015
[25] Ernst, A.T.; Mak, V.H.; Mason, L.A., An exact method for the minimum cardinality problem in the planning of IMRT, INFORMS journal on computing, 21, 4, 562-574, (2009) · Zbl 1243.90272
[26] Focacci, F.; Lodi, A.; Milano, M., Cost-based domain filtering, (), 189-203
[27] T. Gellermann, M. Sellmann, R. Wright, Shorter path constraints for the resource constrained shortest path problem, in: CPAIOR, 2005, pp. 201-216. · Zbl 1133.90404
[28] Gilmore, P.C.; Gomory, R., A linear programming approach to the cutting-stock problem, Operations research, 9, 6, 849-859, (1961) · Zbl 0096.35501
[29] Hamacher, H.; Ehrgott, M., Special section: using discrete mathematics to model multileaf collimators in radiation therapy, Discrete applied mathematics, 152, 1-3, 4-5, (2005)
[30] Kalinowski, T., A duality based algorithm for multileaf collimator field segmentation with interleaf collision constraint, Discrete applied mathematics, 152, 1-3, 52-88, (2005) · Zbl 1078.92035
[31] Kalinowski, T., The complexity of minimizing the number of shape matrices subject to minimal beam-on time in multileaf collimator field decomposition with bounded fluence, Discrete applied mathematics, 157, 9, 2089-2104, (2009) · Zbl 1190.68030
[32] Kamath, S.; Sahni, S.; Li, J.; Palta, J.; Ranka, S., Leaf sequencing algorithms for segmented multileaf collimation, Physics in medicine and biology, 48, 3, 307-324, (2003)
[33] Kamath, S.; Sahni, S.; Palta, J.; Ranka, S., Algorithms for optimal sequencing of dynamic multileaf collimators, Physics in medicine and biology, 49, 1, 33-54, (2003)
[34] Kamath, S.; Sahni, S.; Ranka, S.; Palta, J.; Li, J., Optimal leaf sequencing with elimination of tongue-and-groove underdosage, Physics in medicine and biology, 49, 14, N17-N19, (2004)
[35] Langer, M.; Thai, V.; Papiez, L., Improved leaf sequencing reduces segments or monitor units needed to deliver IMRT using multileaf collimators, Medical physics, 28, 12, 2450-2458, (2001)
[36] Lee, E.K.; Lim, G.J., Optimization in medicine and biology, (2007), Taylor and Francis, Auerbach Publications
[37] Lübbecke, M.E.; Desrosiers, J., Selected topics in column generation, Operations research, 53, 6, 1007-1023, (2005) · Zbl 1165.90578
[38] M. Maher, Analysis of a global contiguity constraint, in: Workshop on Rule-Based Constraint Reasoning and Programming, 2002.
[39] Martin, D.; Francois, S., A generalized permanent labelling algorithm for the shortest path problem with time windows, INFORMS journal on computing, 26, 3, 191-212, (1988) · Zbl 0652.90097
[40] G. Pesant, A regular language membership constraint for finite sequences of variables, in: CP, 2004, pp. 482-495. · Zbl 1152.68573
[41] Que, W.; Kung, J.; Dai, J., ‘tongue-and-groove’ effect in intensity modulated radiotherapy with static multileaf collimator fields, Physics in medicine and biology, 49, 1, 339-405, (2004)
[42] Siochi, R.A.C., Minimizing static intensity modulation delivery time using an intensity solid paradigm, International journal of radiation oncology biology physics, 43, 3, 671-680, (1999)
[43] Taskin, Z.C.; Smith, J.C.; Romeijn, H.E.; Dempsey, J.F., Optimal multileaf collimator leaf sequencing in IMRT treatment planning, Operations research, 58, 3, 674-690, (2010) · Zbl 1228.90171
[44] F. Vanderbeck, Decomposition and column generation for integer programs, Ph.D. Thesis, Université Catholique de Louvain, 1994.
[45] F. Vanderbeck, L. Wolsey, Reformulation and decomposition of integer programs, 2009. URL: www.vtls.com. · Zbl 1187.90207
[46] Wake, G.M.G.H.; Boland, N.; Jennings, L.S., Mixed integer programming approaches to exact minimization of total treatment time in cancer radiotherapy using multileaf collimators, Computers & operations research, 36, 3, 795-810, (2009) · Zbl 1157.90581
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.