Data from: Solution of the Generalized Noah's Ark Problem

The phylogenetic diversity (PD) of a set of species is a measure of the evolutionary distance among the species in the collection, based on a phylogenetic tree. Such a tree is composed of a root, of internal nodes and of leaves that correspond to the set of taxa under study. With each edge of the tree is associated a non-negative branch length (evolutionary distance). If a particular survival probability is associated with each taxon, the PD measure becomes the expected PD measure. In the Noah’s Ark Problem (NAP) introduced by Weitzman (1998), these survival probabilities can be increased at some cost. The problem is to determine how best to allocate a limited amount of resources to maximize the expected PD of the considered species. It is easy to formulate the NAP as a (difficult) nonlinear 0-1 programming problem. The aim of this article is to show that a general version of the NAP (GNAP) can be solved simply and efficiently with any set of edge weights and any set of survival probabilities by using standard mixed-integer linear programming software. The crucial point to move from a nonlinear program in binary variables to a mixed-integer linear program, is to approximate the logarithmic function by the lower envelope of a set of tangents to the curve. Solving the obtained mixed-integer linear program provides not only a near-optimal solution but also an upper bound on the value of the optimal solution. We also applied this approach to a generalization of the Nature Reserve Problem (GNRP) that consists of selecting a set of regions to be conserved so that the expected phylogenetic diversity of the set of species present in these regions is maximized. In this case, the survival probabilities of different taxa are not independent of each other. Computational results are presented to illustrate potentialities of the approach. Near-optimal solutions with hypothetical phylogenetic trees comprising about 4,000 taxa are obtained in a few seconds or minutes of computing time for the GNAP, and in about 30 minutes for the GNRP. In all the cases the average guarantee varies from 0% to 1.20%.

物种集合的系统发育多样性（phylogenetic diversity, PD）是一项以系统发育树（phylogenetic tree）为基础，衡量该集合内物种间进化距离的指标。此类树由根节点、内部节点以及对应研究中分类单元（taxon，复数taxa）集合的叶节点构成。该树的每条边均关联一个非负的分支长度（即进化距离）。若为每个分类单元赋予特定的存活概率，则系统发育多样性指标可转化为期望系统发育多样性。在Weitzman（1998）提出的诺亚方舟问题（Noah’s Ark Problem, NAP）中，可通过投入一定成本提升各分类单元的存活概率。该问题的核心目标为：确定如何最优分配有限资源，以最大化目标物种集合的期望系统发育多样性。不难将NAP建模为一个（难解的）非线性0-1规划问题。本文旨在证明：借助标准混合整数线性规划（mixed-integer linear programming）软件，可通过简洁高效的方式求解诺亚方舟问题的一般化版本（general NAP, GNAP），且该方法可适配任意边权重集合与任意存活概率集合。将二进制变量的非线性规划转化为混合整数线性规划的核心思路，是利用一组曲线切线的下包络来近似对数函数。求解该混合整数线性规划，不仅可获得近似最优解，还能给出最优解数值的上界。我们还将该方法应用于自然保护区问题的一般化版本（general Nature Reserve Problem, GNRP）：该问题需要遴选一组待保护区域，使得这些区域内现存物种的期望系统发育多样性最大化。在此场景下，不同分类单元的存活概率并非相互独立。本文展示了计算结果以说明该方法的应用潜力。针对GNAP，在包含约4000个分类单元的假想系统发育树场景下，可在数秒至数分钟的计算时长内得到近似最优解；针对GNRP，该求解过程耗时约30分钟。所有测试场景中，解的平均保证率介于0%至1.20%之间。