Optimizing the ecological connectivity of landscapes

In this article, we consider the problem of optimizing the connectivity of a landscape under a budget constraint, by improving habitat areas and ecological corridors between them. We model this problem as a discrete optimization problem over graphs, in which vertices represent the habitat areas and arcs represent the connections between them. We propose a new flow-based integer linear programming formulation that improves upon the existing models for this problem. By following an approach similar to Catanzaro et al. for the robust shortest path problem, we design an improved preprocessing algorithm that reduces the size of the graphs on which we compute generalized flows. Computational experiments show the benefits of both contributions, by enabling to solve instances of the problem larger than previous models. These experiments also show that several versions of greedy algorithms perform relatively well in practice, while returning arbitrarily bad solutions in the worst case.

Automated summary

In this article, the problem of optimizing landscape connectivity under a budget constraint is considered. A new flow-based integer linear programming formulation is proposed, improving upon existing models. Computational experiments show the benefits of the proposed formulation and an improved preprocessing algorithm in solving larger instances of the problem. Greedy algorithms perform relatively well in practice but may give arbitrarily bad solutions in the worst case.