A shortest path-based approach to the multileaf collimator sequencing problem

作者：Cambazard Hadrien; O' Mahony Eoin; O' Sullivan Barry

来源：Discrete Applied Mathematics, 2012, 160(1-2): 81-99.

DOI：10.1016/j.dam.2011.09.008

• Combinatorial optimisation
• Constraint programming
• Operations research
• Intensity-modulated radiotherapy

The rnultileaf 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.

• 出版日期2012-1