An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem

Algorithms

Céline Engelbeen¹  Daniele Catanzaro² 

[1] Institut Catholique des Hautes Etudes Commerciales (ICHEC), Boulevard Brand Whitlock 2, 1150 Brussels, Belgium;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;

关键词: matrix decomposition;    minimum cardinality segmentation problem;    mixed integer linear programming;    intensity-modulated radiation therapy;    multileaf collimator;   

DOI  :  10.3390/a8040999

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown