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

Davaatseren Baatar, Natashia Boland, Sebastian Brand, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

28 Citations (Scopus)

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 languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings
Pages1-15
Number of pages15
Publication statusPublished - 20 Dec 2007
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007 - Brussels, Belgium
Duration: 23 May 200726 May 2007
Conference number: 4th
https://link.springer.com/book/10.1007/978-3-540-72397-4 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4510 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007
Abbreviated titleCPAIOR 2007
Country/TerritoryBelgium
CityBrussels
Period23/05/0726/05/07
Internet address

Cite this