An integer linear programming formulation for the minimum cardinality segmentation problem
Summary: In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an \(\mathcal{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.
- An exact method for the minimum cardinality problem in the treatment planning of intensity-modulated radiotherapy
- Minimum Cardinality Matrix Decomposition into Consecutive-Ones Matrices: CP and IP Approaches
- CP and IP approaches to cancer radiotherapy delivery optimization
- Minimizing the number of apertures in multileaf collimator sequencing with field splitting
- A network approach for segmentation in intensity modulated arc therapy
- A new algorithm for optimal multileaf collimator field segmentation
- A shortest path-based approach to the multileaf collimator sequencing problem
- An exact method for the minimum cardinality problem in the treatment planning of intensity-modulated radiotherapy
- Constrained decompositions of integer matrices and their applications to intensity modulated radiation therapy
- CP and IP approaches to cancer radiotherapy delivery optimization
- Decomposition of integer matrices and multileaf collimator sequencing
- Exact algorithms for minimum routing cost trees
- Faster optimal algorithms for segment minimization with small maximal value
- scientific article; zbMATH DE number 3577263 (Why is no real title available?)
- scientific article; zbMATH DE number 1349588 (Why is no real title available?)
- Iterative variable aggregation and disaggregation in IP: an application
- Mathematical optimization in intensity modulated radiation therapy
- Mersenne twister
- Minimum Cardinality Matrix Decomposition into Consecutive-Ones Matrices: CP and IP Approaches
- Mixed integer programming approaches to exact minimization of total treatment time in cancer radiotherapy using multileaf collimators
- Network flows. Theory, algorithms, and applications.
- Nonnegative integral subset representations of integer sets
- Twisted GFSR generators
This page was built for publication: An integer linear programming formulation for the minimum cardinality segmentation problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736729)
