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）集合的叶节点共同构成。树的每条边均关联有非负的分支长度（branch length，即进化距离）。若为每个分类单元赋予特定的存活概率（survival probability），则传统的系统发育多样性指标可拓展为期望系统发育多样性指标。1998年魏茨曼（Weitzman）提出的诺亚方舟问题（Noah’s Ark Problem, NAP）中，可通过投入一定成本提升各类群的存活概率。该问题的核心目标为：确定如何最优分配有限资源，以最大化所考量物种的期望系统发育多样性。不难发现，NAP可被建模为一个极具挑战性的非线性0-1规划问题。本文旨在证明，借助标准混合整数线性规划（mixed-integer linear programming）软件，可通过简便高效的方式求解广义诺亚方舟问题（Generalized Noah’s Ark Problem, GNAP），且该方法适用于任意边权重集合与任意存活概率集合。将二进制变量下的非线性规划转化为混合整数线性规划的关键所在，在于利用一组曲线切线（tangents）的下包络线（lower envelope）近似对数函数（logarithmic function）。求解所得混合整数线性规划，不仅可得到近似最优解，还能给出最优解目标值的理论上界。我们还将该方法应用于广义自然保护区问题（Generalized Nature Reserve Problem, GNRP）——该问题要求选取待保护的区域集合，最大化这些区域内现存物种的期望系统发育多样性。在此场景下，不同分类单元的存活概率并非相互独立。文末给出了计算实验结果，以验证该方法的应用潜力。针对广义诺亚方舟问题，在包含约4000个分类单元的假想系统发育树场景下，可在数秒或数分钟内得到近似最优解；而针对广义自然保护区问题，该求解过程耗时约30分钟。所有测试场景中，解的平均保证率介于0%至1.20%之间。