Next Article in Journal
Semi-Supervised Classification Based on Mixture Graph
Next Article in Special Issue
Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment
Previous Article in Journal
Some Matrix Iterations for Computing Generalized Inverses and Balancing Chemical Equations
Previous Article in Special Issue
Automatic Classification of Protein Structure Using the Maximum Contact Map Overlap Metric
Due to scheduled maintenance work on our core network, there may be short service disruptions on this website between 16:00 and 16:30 CEST on September 25th.
Article

An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem

1
Louvain 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, Belgium
2
Institut Catholique des Hautes Etudes Commerciales (ICHEC), Boulevard Brand Whitlock 2, 1150 Brussels, Belgium
*
Author to whom correspondence should be addressed.
Academic Editors: Giuseppe Lancia and Alberto Policriti
Algorithms 2015, 8(4), 999-1020; https://0-doi-org.brum.beds.ac.uk/10.3390/a8040999
Received: 27 June 2015 / Revised: 23 September 2015 / Accepted: 2 November 2015 / Published: 11 November 2015
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
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. View Full-Text
Keywords: matrix decomposition; minimum cardinality segmentation problem; mixed integer linear programming; intensity-modulated radiation therapy; multileaf collimator matrix decomposition; minimum cardinality segmentation problem; mixed integer linear programming; intensity-modulated radiation therapy; multileaf collimator
Show Figures

Figure 1

MDPI and ACS Style

Catanzaro, D.; Engelbeen, C. An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem. Algorithms 2015, 8, 999-1020. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040999

AMA Style

Catanzaro D, Engelbeen C. An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem. Algorithms. 2015; 8(4):999-1020. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040999

Chicago/Turabian Style

Catanzaro, Daniele, and Céline Engelbeen. 2015. "An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem" Algorithms 8, no. 4: 999-1020. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040999

Find Other Styles

Article Access Map by Country/Region

1
Only visits after 24 November 2015 are recorded.
Back to TopTop