Abstract
We consider the problem of decomposing an integer matrix into a positively weighted sum of binary matrices that have the consecutiveones property. This problem is wellknown 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 setups required to deliver the planned treatment). Minimising the former is known to be easy. However finding a decomposition of minimal cardinality is NPhard. Progress so far has largely been restricted to heuristic algorithms, mostly using linear programming, integer programming and combinatorial enumerative methods as the solving technologies. 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 language  English 

Title of host publication  Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems  4th International Conference, CPAIOR 2007, Proceedings 
Pages  115 
Number of pages  15 
Publication status  Published  20 Dec 2007 
Externally published  Yes 
Event  International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007  Brussels, Belgium Duration: 23 May 2007 → 26 May 2007 Conference number: 4th https://link.springer.com/book/10.1007/9783540723974 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  4510 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007 

Abbreviated title  CPAIOR 2007 
Country/Territory  Belgium 
City  Brussels 
Period  23/05/07 → 26/05/07 
Internet address 
