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

Baatar, D.;Boland, N.;Brand, S.;Stuckey, P.J.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Baatar, D.
    Author
  • Boland, N.
    Author
  • Brand, S.
    Author
  • Stuckey, P.J.
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Baatar, D., Boland, N., Brand, S., & Stuckey, P. J. (2007). Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 1-15). Springer-verlag. https://hdl.handle.net/2078.5/230961