Solving conservation planning problems with integer linear programming

摘要

Deciding where to implement conservation actions in order to meet conservation targets efficiently is an important component of systematic conservation planning. Mathematical optimisation is a quantitative and transparent framework for solving these problems. Despite several advantages of exact methods such as integer linear programming (ILP), most conservation planning problems to date have been solved using heuristic approaches such as simulated annealing (SA). We explain how to implement common conservation planning problems (e.g. Marxan and Marxan With Zones) in an ILP framework and how these formulations can be extended to account for spatial dependencies among planning units, such as those arising from environmental flows (e.g. rivers). Using simulated datasets, we demonstrate that ILP outperforms SA with respect to both solution quality (how close it is to optimality) and processing time over a range of problem sizes. For modestly sized quadratic problems (100,000 spatial units and 10 species), for example, a processing time of approximately 14 h was required for SA to achieve a solution within 19% of optimality, while ILP achieved solutions within 0.5% of optimality within 30 s. For the largest quadratic problems we evaluated processing time exceeding one day was required for SA to achieve a solution within 49% of optimality, while ILP achieved solutions within 0.5% of optimality in approximately one hour. Heuristics are conceptually simple and can be applied to large and non-linear objective functions but unlike ILP, produce solutions of unknown quality. We also discuss how ILP approaches also facilitate quantification of trade-off curves and sensitivity analysis. When solving linear or quadratic conservation planning problems we recommend using ILP over heuristic approaches whenever possible. (C) 2016 Elsevier B.V. All rights reserved.