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

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

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 proceeding › Conference Paper › Research › peer-review

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	https://link.springer.com/book/10.1007/978-3-540-72397-4 (Proceedings)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Cite this

Baatar, D., Boland, N., Brand, S., & Stuckey, P. J. (2007). Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings (pp. 1-15). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4510 LNCS).

Baatar, Davaatseren ; Boland, Natashia ; Brand, Sebastian ; Stuckey, Peter J. / Minimum cardinality matrix decomposition into consecutive-ones matrices : CP and IP approaches. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings. 2007. pp. 1-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cba9146189a940d6a3ec27d5f47f4d44,

title = "Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches",

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.",

author = "Davaatseren Baatar and Natashia Boland and Sebastian Brand and Stuckey, {Peter J.}",

year = "2007",

month = dec,

day = "20",

language = "English",

isbn = "354072396X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "1--15",

booktitle = "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007, CPAIOR 2007 ; Conference date: 23-05-2007 Through 26-05-2007",

url = "https://link.springer.com/book/10.1007/978-3-540-72397-4",

}

Baatar, D, Boland, N, Brand, S & Stuckey, PJ 2007, Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches. in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4510 LNCS, pp. 1-15, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007, Brussels, Belgium, 23/05/07.

Minimum cardinality matrix decomposition into consecutive-ones matrices : CP and IP approaches. / Baatar, Davaatseren; Boland, Natashia; Brand, Sebastian; Stuckey, Peter J.

Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings. 2007. p. 1-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4510 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Minimum cardinality matrix decomposition into consecutive-ones matrices

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2007

AU - Baatar, Davaatseren

AU - Boland, Natashia

AU - Brand, Sebastian

AU - Stuckey, Peter J.

N1 - Conference code: 4th

PY - 2007/12/20

Y1 - 2007/12/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=37149027934&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:37149027934

SN - 354072396X

SN - 9783540723967

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 15

BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings

Y2 - 23 May 2007 through 26 May 2007

ER -

Baatar D, Boland N, Brand S, Stuckey PJ. Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings. 2007. p. 1-15. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

Abstract

Publication series

Conference

UN SDGs

Other files and links

Cite this