An exact method for the minimum cardinality problem in the treatment planning of intensity-modulated radiotherapy

In this paper, we introduce an exact method based on constraint programming ideas for a combinatorial optimization problem that arises from the treatment planning of intensity-modulated radiotherapy–the minimum cardinality problem (MCP). The MCP is to find a decomposition of a given integer matrix into a weighted sum of binary matrices with consecutive ones, such that the number of such binary matrices is minimised. We compare our method with two recent exact methods for the same problem and a recent exact method for a special case of the problem. Numerical results are presented that indicate that our method is computationally more efficient than the three existing methods.