Conference Proceedings

Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches

Davaatseren Baatar, Natashia Boland, Sebastian Brand, Peter J Stuckey, P VanHentenryck (ed.), L Wolsey (ed.)

INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS, PROCEEDINGS | SPRINGER-VERLAG BERLIN | Published : 2007

Abstract

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 (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 b..

View full abstract