182
the CYB and DCoH3 regions, the optimal sets only overlap in two countries:
MalaysiaandPhilippines.IfwenowmaximizeSDinstead,thentheoptimalset
includes thesetwocountries, the thirdone preferredby the PD-DCoH3set
(Indonesia),andthefourthonebythePD-CYBset(India).Theunionofthespecies
sets for the selected areas contains seven species.
Ifbudgetdataisavailable,thenwehaveabudgetedreserveselectionproblem.
Here, preserving these species in each country comes at a cost and we need to select
thosecountriesthatmaximizeSDwithinanallocatedbudget.
Computational Methods in Conservation Planning
ThealgorithmstosolvetheaforementionedProblems1–5arethosethatareguaran-
teedtoproduceanoptimalsolution,oftenreferredtoasexactalgorithms,andthose
that are not. The former includes algorithms that are based on integer programming
anddynamicprogramming,whereasthelattercomprisegreedyalgorithms,approx-
imation algorithms and algorithms based on simulated annealing. We will start with
greedy algorithms, as they are simple and probably most widely applied in conser-
vation planning.
Greedy Algorithms
Greedy algorithms are a simple and general heuristic strategy but, usually, do not
guarantee optimal solutions. Kirkpatrick ( 1983 ) was probably the first to apply a
greedyalgorithmtofindasolutiontoProblem4,thesimplereserveselection,but
Problem 5 (Budgeted Reserve Selection)
Given a split set for ntaxadistributedonm areas and conservation costs for
eacharea,findasubsetofareaswhosetotalconservationcostsdonotexceed
apredefinedbudgetwhilemaximizingSD.Table 2 Fourcountries
maximizingPDontheCYB
tree(firstcolumn),PDonthe
DCoH3 tree (second
column), and SD on the split
network (third column)
PD–CYB PD–DCoH3 SD
Malaysia (3) Indonesia(3) Malaysia (3)
Philippines (2) Malaysia (3) Philippines (2)
SriLanka(1) Philippines (2) Indonesia(3)
India(2) Vietnam(2) India(2)
Highlighted in boldface are the countries present in all
optimal sets. The number of species present in the country
is given in bracketsO. Chernomor et al.