296
Hugh Possingham, Ian Ball, and Sandy Andelman
a ij = Ά
1 if species j occurs in site i
0 otherwise
for i = 1, . . . m and j = 1, . . ., n
Next, define a control variable that determines whether a site is included in the
reserve, as the vector X with dimension m and elements x i , given by
x i = Ά
1 if site i is included in the reserve
0 otherwise
for i = 1, . . . , m
With these definitions, the minimum representation problem is
minimize
m
͚
i=1
x i (minimize the number of sites in the reserve system)
subject to
m
͚
i=1
a ij x i ≥ 1, for j = 1, . . ., n (subject to each species being represented at least once)
where a ij , x i ∈ {0,1}
This is the integer linear programming formulation of the set-covering problem.
It is NP-complete so that the difficulty of guaranteeing an optimum solution
increases exponentially with the number of constraints n (Garey and Johnson
1979).
Solving the Minimum Representation Problem:
Traditional Methods
In the context of nature reserve design, the minimum-representation problem has
been tackled by several authors, in a number of different ways. Kirkpatrick (1983)
was first to define the problem and used a heuristic method to find a solution. Such
methods rank each potential reserve site according to a set of criteria and then
reserve the highest-ranking site. The remaining sites are ranked again and the
process continued until all species are represented. Originally, the criterion used
in ranking was the number of species in a site not yet represented in the reserve
system. Other criteria (e.g., the location of rare species) or combinations of
criteria have since been used (e.g., Rebelo and Siegfried 1992; Nicholls and
Margules 1993).
As shown above, this approach guarantees a quick answer, but it does not
ensure an optimal one (Possingham et al. 1993; Underhill 1994). Another approach to the problem has been to express it in the form of an integer linear
program (ILP) and then to use standard mathematical programming techniques
such as the branch-and-bound method to find the optimal solution (Cocks and
Baird 1989; Church et al. 1996). Pressey and co-workers (1997) compared a
variety of heuristic methods (variations of rarity and greedy algorithms) with the
optimal solution found by integer linear programming. The ILP package used a
Hugh Possingham, Ian Ball, and Sandy Andelman
a ij = Ά
1 if species j occurs in site i
0 otherwise
for i = 1, . . . m and j = 1, . . ., n
Next, define a control variable that determines whether a site is included in the
reserve, as the vector X with dimension m and elements x i , given by
x i = Ά
1 if site i is included in the reserve
0 otherwise
for i = 1, . . . , m
With these definitions, the minimum representation problem is
minimize
m
͚
i=1
x i (minimize the number of sites in the reserve system)
subject to
m
͚
i=1
a ij x i ≥ 1, for j = 1, . . ., n (subject to each species being represented at least once)
where a ij , x i ∈ {0,1}
This is the integer linear programming formulation of the set-covering problem.
It is NP-complete so that the difficulty of guaranteeing an optimum solution
increases exponentially with the number of constraints n (Garey and Johnson
1979).
Solving the Minimum Representation Problem:
Traditional Methods
In the context of nature reserve design, the minimum-representation problem has
been tackled by several authors, in a number of different ways. Kirkpatrick (1983)
was first to define the problem and used a heuristic method to find a solution. Such
methods rank each potential reserve site according to a set of criteria and then
reserve the highest-ranking site. The remaining sites are ranked again and the
process continued until all species are represented. Originally, the criterion used
in ranking was the number of species in a site not yet represented in the reserve
system. Other criteria (e.g., the location of rare species) or combinations of
criteria have since been used (e.g., Rebelo and Siegfried 1992; Nicholls and
Margules 1993).
As shown above, this approach guarantees a quick answer, but it does not
ensure an optimal one (Possingham et al. 1993; Underhill 1994). Another approach to the problem has been to express it in the form of an integer linear
program (ILP) and then to use standard mathematical programming techniques
such as the branch-and-bound method to find the optimal solution (Cocks and
Baird 1989; Church et al. 1996). Pressey and co-workers (1997) compared a
variety of heuristic methods (variations of rarity and greedy algorithms) with the
optimal solution found by integer linear programming. The ILP package used a