CP and IP approaches to cancer radiotherapy delivery optimization

Davaatseren Baatar, Natashia Boland, Sebastian Brand, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)


We consider the problem of decomposing an integer matrix into a positively weighted sum of binary matrices that have the consecutive-ones property. This problem is well-known and of practical relevance. It has an important application in cancer radiation therapy treatment planning: the sequencing of multileaf collimators to deliver a given radiation intensity matrix, representing (a component of) the treatment plan. Two criteria characterise the efficacy of a decomposition: the beamon time (the length of time the radiation source is switched on during the treatment), and the cardinality (the number of machine set-ups required to deliver the planned treatment). Minimising the former is known to be easy. However finding a decomposition of minimal cardinality is NP-hard. Progress so far has largely been restricted to heuristic algorithms, mostly using linear programming, integer programming and combinatorial enumerative methods as the solving approaches. We present a novel model, with corresponding constraint programming and integer programming formulations. We compare these computationally with previous formulations, and we show that constraint programming performs very well by comparison.

Original languageEnglish
Pages (from-to)173-194
Number of pages22
Issue number2
Publication statusPublished - Apr 2011
Externally publishedYes


  • Integer programming
  • Intensity-modulated radiation therapy
  • Modelling
  • Multileaf collimator leaf sequencing
  • Search
  • Symmetry-breaking

Cite this