An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem
In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-11-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/8/4/999 |
| _version_ | 1828230124685754368 |
|---|---|
| author | Daniele Catanzaro Céline Engelbeen |
| author_facet | Daniele Catanzaro Céline Engelbeen |
| author_sort | Daniele Catanzaro |
| collection | DOAJ |
| description | In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set of binary matrices satisfying the consecutive ones property. We show how to transform the MCSP into a combinatorial optimization problem on a weighted directed network and we exploit this result to develop an integer linear programming formulation to exactly solve it. Computational experiments show that the lower bounds obtained by the linear relaxation of the considered formulation improve upon those currently described in the literature and suggest, at the same time, new directions for the development of future exact solution approaches to the problem. |
| first_indexed | 2024-04-12T18:44:43Z |
| format | Article |
| id | doaj.art-c1fbe186b30542a28c7e7c99a0cfafb0 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-12T18:44:43Z |
| publishDate | 2015-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-c1fbe186b30542a28c7e7c99a0cfafb02022-12-22T03:20:40ZengMDPI AGAlgorithms1999-48932015-11-0184999102010.3390/a8040999a8040999An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation ProblemDaniele Catanzaro0Céline Engelbeen1Louvain School of Management, Center for Operations Research and Econometrics (CORE), Université Catholique de Louvain, Chaussée de Binche 151, bte M1.01.01, 7000 Mons, BelgiumInstitut Catholique des Hautes Etudes Commerciales (ICHEC), Boulevard Brand Whitlock 2, 1150 Brussels, BelgiumIn this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set of binary matrices satisfying the consecutive ones property. We show how to transform the MCSP into a combinatorial optimization problem on a weighted directed network and we exploit this result to develop an integer linear programming formulation to exactly solve it. Computational experiments show that the lower bounds obtained by the linear relaxation of the considered formulation improve upon those currently described in the literature and suggest, at the same time, new directions for the development of future exact solution approaches to the problem.http://www.mdpi.com/1999-4893/8/4/999matrix decompositionminimum cardinality segmentation problemmixed integer linear programmingintensity-modulated radiation therapymultileaf collimator |
| spellingShingle | Daniele Catanzaro Céline Engelbeen An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem Algorithms matrix decomposition minimum cardinality segmentation problem mixed integer linear programming intensity-modulated radiation therapy multileaf collimator |
| title | An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem |
| title_full | An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem |
| title_fullStr | An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem |
| title_full_unstemmed | An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem |
| title_short | An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem |
| title_sort | integer linear programming formulation for the minimum cardinality segmentation problem |
| topic | matrix decomposition minimum cardinality segmentation problem mixed integer linear programming intensity-modulated radiation therapy multileaf collimator |
| url | http://www.mdpi.com/1999-4893/8/4/999 |
| work_keys_str_mv | AT danielecatanzaro anintegerlinearprogrammingformulationfortheminimumcardinalitysegmentationproblem AT celineengelbeen anintegerlinearprogrammingformulationfortheminimumcardinalitysegmentationproblem AT danielecatanzaro integerlinearprogrammingformulationfortheminimumcardinalitysegmentationproblem AT celineengelbeen integerlinearprogrammingformulationfortheminimumcardinalitysegmentationproblem |