Minimum Cardinality Matrix Decomposition into Consecutive-Ones Matrices: CP and IP Approaches
Lists
Only you see this
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 beam-on 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.
BibTeX
@inproceedings{baatar2007minimum,
author = {Davaatseren Baatar and Natashia Boland and Sebastian Brand and Peter J. Stuckey},
title = {{Minimum Cardinality Matrix Decomposition into Consecutive-Ones Matrices: CP and IP Approaches}},
booktitle = {CPAIOR},
year = {2007},
doi = {10.1007/978-3-540-72397-4\_1},
}Loading related content...