183under the species richness concept. His greedy algorithm coined “complementarity
principle”firstidentifiesthemostspecies-richarea.Inthesecondstep,itfindsthe
area,which“adds”themostnumbersofnewspeciestothefirstlychosenarea.This
is repeated until k areas are obtained. Such a complementarity principle has been
appliedtomaximizePD(Faith 1992 )andalsoappliedelsewhere(e.g.,Vane-Wright
et al. 1991 ;Presseyetal. 1997 ).Recently,BordewichandSemple( 2008 ) have
proventhatthegreedyalgorithmappliedtoProblem 5 underPDwillgeneratea
solutionthathasatleast~63%ofthePDoftheoptimalsolution,whichisthebest
possibleapproximationratio.
The only case, where a greedy algorithm delivers the optimal solution is the
taxonselection(Problem1)underPDontrees(PardiandGoldman 2005 ; Steel
2005 ). An efficient implementation of such a greedy algorithm (Minh et al. 2006 )
findsasolutionfortreeswithmillionsoftaxawithinsecondsonastandardPC.
Greedyalgorithmshavebeenfurtherexaminedinconservationbiology(Moulton
et al. 2007 ; Bordewich et al. 2008 ).
ObviouslygreedyalgorithmscanbeappliedforProblems1–5tomaximize
SD.Thegeneralideaistostartwithonetarget(eithertaxonorarea)havingthe
highestSD.Wethenchoosethesecondtarget“adding”themostSDwhilestillsat-
isfying the constraints (budget or viability constraints). We repeat this step until no
furthertargetcanbeadded(e.g.,exceedingktargetsforProblem1,3,and 4 or
exceedingthebudgetforProblem 2 and5).Asanillustrationthegreedyalgorithm
isappliedforProblem 4 tofindfourcountriesshowingthehighestpheasantSDfor
thesplitnetwork(Fig.2b) and known geographical distribution (Table 1 ) as fol-
lows.MalaysiaisfirstselectedasitcontainsthehighestSD.Philippines,Indonesia,
andIndiaareselectedinthenextsteps.Inthisparticularexamplethegreedyalgo-
rithm happens to obtain the optimal set of four countries (Table 2 ).
Integer Programming
IntegerProgramming(IP;Dantzigetal. 1954 ; Gomory 1958 ) is a widely used and
powerful optimization technique to solve a variety of decision-making problems
(Wolsey 1998 ;Jüngeretal. 2010 ).IPmethodsmaximizeorminimizealinearobjec-
tive function subject to linear constraints (equalities or inequalities) when one or
morevariablesarerestrictedtobeintegers.TheoreticallysolvingIPisNP-hard.
However,thankstopowerfulsolverslikeCPLEX( 2012 )andGUROBI(Gurobi
OptimizationInc. 2013 ), problems with thousands of variables and constraints can
besolvedoptimallywithinreasonabletime(Jüngeretal. 2010 ; and references
therein).
ThefirstapplicationofIPinconservationproblemsgoesbackto(Cocksand
Baird 1989 ),whosolvedthereserveselection(Problem4)underspeciesrichness.
SuchIPformulationshavebeenextendedtomorerealisticscenarios(Underhill
1994 ; Church et al. 1996 ;Possinghametal. 2000 ),tomaximizePD(Rodriguesand
Gaston 2002 ;Rodriguesetal. 2005 ),andtomaximizeSD(Minhetal. 2010 ).
Split Diversity: Measuring and Optimizing Biodiversity Using Split Networks