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: Accepted by John Hooker, Area Editor for Constraint Programming and Optimization; received September 2007; revised June 2008; accepted September 2008. Published online in Articles in Advance February 5, 2009.

1. Introduction

The minimum cardinality problem (MCP) arose from the treatment planning of intensity-modulated radiotherapy (IMRT) using multileaf collimators. The problem is also known as the minimal number of shapes problem (see Baatar et al. 2005, Ehrgott et al. 2008). We first explain the problem mathematically.

DEFINITION 1. We define B = [(b).sub.[i,j]] [member of] [{0,1}.sup.(mxn)] to be a Consecutive-1 (C-1) matrix if it contains at most one string of ones; i.e., there is at most one j such that [B.sub.[i,j]] < [B.sub.[i,j+1]].

We use B to denote the set of all C-1 matrices. Given any matrix A = [(a).sub.[i,j]] [member of] [Z.sub.+.sup.(mxn)], the MCP is to find a decomposition of A that uses the minimum number of C-1 matrices; i.e., it is to solve

PROBLEM 1.

min k s.t. [[mu].sub.1][B.sub.1] + [[mu].sub.2][B.sub.2] + ... + [[mu].sub.k][B.sub.k] = A,

where [[mu].sub.l] [member of] [Z.sub.+] and [B.sub.l] [member of] B, for l= 1,...,k

We refer to this as the k-decomposition of A. In the rest of the paper we use [sigma](A) to denote the optimal decomposition of A. Using terminology of intensity-modulated radiotherapy, we refer to A as the intensity matrix; [mu] the MU sequence (for monitor unit sequence, also referred to as the intensity vector); and [B.sub.v], for l = 1,..., k, the shape matrices. The MCP is to minimize the number of shape matrices needed to decompose A. For more background in MCP and related problems in the context of IMRT, see Ahuja and Hamacher (2005), Baatar et al. (2005, 2007), Ehrgott et al. (2008), Engel (2005), Kalinowski (2004), Langcr et al. (2001), Nufsbaum (2006), Taskin et al. (2007), and Xia and Verhey (1998).

We now introduce some definitions and notation we shall use throughout the paper. Let M = {1,..., m} and N = {1,..., n}. We first obtain a difference matrix, D, of order m x (n +1), in the following manner. We add two zero-columns to A by setting [a.sub.[i,0]] = [a.sub.i,[n+1]] = 0 for all i [member of] M, and obtain D by setting

[d.sub.ij] = [a.sub.ij] - [a.sub.[i,j-1]], i[member of]M, j[member of]N[union]{n + 1}.

For each row i of A, we define...