Heuristic and optimal solutions for set-covering problems in conservation biology

Area-selection methods have recently gained prominence in conservation biology. A typical problem is to identify the minimum number of areas required to represent all species over some geographic region. Iterative heuristic methods have been developed by conservation scientists to solve these problems, although the solutions cannot be guaranteed to be optimal. Although optimal solutions can often be found, heuristics continue to be popular as they are perceived to be faster and more transparent as they are intuitively easy to understand. We used distributional data for 1921 bird species, 939 mammal species, 405 snake species, and 617 amphibian species compiled at the Zoological Museum, Univ. of Copenhagen for all 1° cells of mainland sub-Saharan Africa to compare the quality of the solutions found using two heuristic methods (simple-greedy algorithm and a progressive-rarity algorithm) with optimal solutions. We found that the heuristic methods considered here often provide solutions as good as optimal solutions. Even in those cases where the optimal solutions were better the difference was relatively small, with the heuristics providing solutions requiring a 2–10% increase in area selected compared with the optimal solution, which, importantly, represented an increase of <1% of the total area. Our study also suggests that the heuristic algorithms performed least well for datasets with few single cell endemics and taxa that tend to have larger range sizes. Despite the good quality of solutions using heuristics there was no time penalty associated with finding optimal solutions for the problems considered here, suggesting that the major obstacle to their use is making optimal methods accessible to conservation biologists. We encourage conservation biologists to work with operations researchers and so gain the benefit of their expertise and experience in solving these kinds of problems.