Fast and accurate MARXAN: the return of the ILP (Integer Linear Programming)
In Beyer et al (Ecological Modelling, 2016), Yann and co-authors propose an efficient integer linear program (ILP) to solve conservation planning problems for MARXAN and MARXAN with zones.
Because conservation planning problems are not linear, an accurate linearization was required to get an efficient ILP model, i.e. running in a good computing time. Yann’s contribution was to propose an efficient linearization, and to clarify the advantages of using ILP compared to the current heuristic used in MARXAN (simulated annealing). ILP is an exact method so it always provides optimal solutions. Moreover, ILP allows to easily integrate multiple objectives and to deal with unknown instances by using robust approaches.
In conservation, ILP has been avoided for the past decades because of long computational running times. However, recent versions of linear programming software solutions include new algorithms such as new branch-and-cuts / dynamic search processes, reducing the computation time required to solve ILP problems by millions compared to the first versions.
The results are impressive and you should definitely have a look if your conservation planning problem takes too long to solve or you are uncertain about the quality of the solutions! Congratulations Yann and team!
Hawthorne L. Beyer, Yann Dujardin, Matthew E. Watts, Hugh P. Possingham, Solving conservation planning problems with integer linear programming, Ecological Modelling, Volume 328, 24 May 2016, Pages 14-22, ISSN 0304-3800, http://dx.doi.org/10.1016/j.ecolmodel.2016.02.005.