184
Here,weshowhowtomodelbiodiversityoptimizationproblems1–5inIPpar-
lance,whichallowsavailableIPsoftwarepackagestosolvetheproblem.Wefirst
introducesomenotationsanddefinitionsandfurtherexemplifyIPformulationsfor
Problems1–5usingthepheasantdataset.
IP for Taxon Selection Problems
Given a set of ntaxa,weencodeasubsetS by an n-element binary vector with
entriesof 0 and 1 indicatingtheabsenceandpresenceofthecorrespondingtaxain
S.Theelementsofthisvectorarecalledtaxonvariables.Forthepheasantdataset
therearetentaxonvariablesxPB, xPC, xPE, xPG, xPI, xPM, xGG, xGL, xGS, xGV (indices fol-
low initials of species names). We say that a split σ = A|B is preserved in S if A and
BeachcontainatleastonetaxonfromS.Foreachsplitσ we introduce a binary split
variable yσ, where yσ = 1 if σ is preserved in S and 0 otherwise.
Eachyσisfullyidentifiedfromtaxonvariablesbytwosplitconstraintsasfol-
lows. σ 1 is a trivial split that separates P. bicalcaratumfromtheremainingtaxa.σ 1
is preserved (i.e. y 1 = 1) if P. bicalcaratumandatleastanothertaxonarepreserved
(seeFig.2aforthedefinitionofthesplits).Thisconditionisexpressedbytwo
inequalities:
yx^11 ≤≤PB,yxPC++xxPE PG++xxPI PM++xxGG GL++xxGS GV
Infact,thesecondinequalityalwaysholdsbecausek ≥ 2 and thus is ignored. Now
consider the non-trivial split σ 17 , which separates G. gallus, G. lafayetii, and G.
variusfromtheremainingtaxa.σ 17 is preserved if at least one of G. gallus, G. lafay-
etii, and G. variusandoneoftheremainingtaxaarepreserved.Therefore,
yx^17 ≤+GG xxGL+≤GV,yx^17 PB++xxPC PI++xxPG PE++xxPM GS
The remaining split constraints are listed in Table 3.
Based on split variables one can rewrite SD of S as:
SD()Sy=∑
σλσσ
(1)where λσ is the weight of split σ.Thisistheobjectivefunctionthatwewanttomaxi-
mizeforallproblems(1–5).
InthetaxonselectionProblem 1 thesizeofanoptimalsubsetisconstrainedbya
predefined number k, meaning that:
xxPB++PC xxPE++PG xxPI++PM xxGG++GL xxGS+≤GV k (2)
WealsorequirethattaxonandsplitvariablesarebinaryO. Chernomor et al.