This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ernst, A. T. Articles by Mason, L. R. Search for Related Content

An Exact Method for the Minimum Cardinality Problem in the Treatment Planning of Intensity-Modulated Radiotherapy

CSIRO Mathematical and Information Sciences, Clayton, Victoria 3169, Australia
School of Information Technology, Deakin University, Burwood, Victoria 3125, Australia
School of Information Technology, Deakin University, Burwood, Victoria 3125, Australia
andreas.ernst{at}csiro.au
vicky.mak{at}deakin.edu.au
luke.mason{at}deakin.edu.au

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.

Key words: health care; treatment; mathematics; combinatorics
History: received September 2007; revised June 2008; accepted September 2008.