Solving the probabilistic reserve selection problem

The Reserve Selection Problem consists in selecting certain sites among a set of potential sites for biodiversity protection. In many models of the literature, the species present and able to survive in each site are supposed to be known. Here, for every potential site and for every species considered, only the probability that the species survives in the site is supposed to be known. The problem to select, under a budgetary constraint, a set of sites which maximizes the expected number of species is known in the literature under the name of probabilistic reserve selection problem. In this article, this problem is studied with species weighting to deal differently with common species and rare species. A spatial constraint is also considered preventing to obtain too fragmented reserve networks. As in Polasky et al. (2000), the problem is formulated by a nonlinear mathematical program in Boolean variables. Camm et al. (2002) developed a mixed-integer linear programming approximation that may be solved with standard integer programming software. The method gives tight approximate solutions but does not allow to tell how far these solutions are from the optimum. In this paper, a slightly different approach is proposed to approximate the problem. The interesting aspect of the approach, which also uses only standard mixed-integer programming software, is that it leads, not only to an approximate solution, but also to an upper limit on the true optimal value. In other words, the method gives an approximate solution with a guarantee on its accuracy. The linear reformulation is based on an upper approximation of the logarithmic function by a piecewise-linear function. The approach is very effective on artificial instances that include up to 400 sites and 300 species. Within an average CPU time of about 12min, near-optimal solutions are obtained with an average relative error, in comparison to the optimum, of less than 0.2%.