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 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 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 | 1-15 |
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/978-3-540-72397-4 (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) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
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 |
|