- Title
- Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches
- Creator
- Baatar, Davaatseren; Boland, Natashia; Brand, Sebastian; Stuckey, Peter J.
- Relation
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems : 4th International Conference, CPAIOR 2007 Brussels, Belgium, May 23-26, 2007 : Proceedings p. 1-15
- Relation
- Lecture Notes in Computer Science 4510
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-72397-4_1
- Publisher
- Springer
- Resource Type
- book chapter
- Date
- 2007
- Description
- 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.
- Subject
- consecutive-ones matrices; cardinality; intensity-modulated radiation therapy; constraint programming
- Identifier
- http://hdl.handle.net/1959.13/939383
- Identifier
- uon:12790
- Identifier
- ISBN:9783540723967
- Language
- eng
- Hits: 2634
- Visitors: 2611
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|