Cargando…

Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems

The resources available for conserving biodiversity are limited, and so protected areas need to be established in places that will achieve objectives for minimal cost. Two of the main algorithms for solving systematic conservation planning problems are Simulated Annealing (SA) and exact integer line...

Descripción completa

Detalles Bibliográficos
Autores principales: Schuster, Richard, Hanson, Jeffrey O., Strimas-Mackey, Matthew, Bennett, Joseph R.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: PeerJ Inc. 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7261139/
https://www.ncbi.nlm.nih.gov/pubmed/32518737
http://dx.doi.org/10.7717/peerj.9258
_version_ 1783540451276488704
author Schuster, Richard
Hanson, Jeffrey O.
Strimas-Mackey, Matthew
Bennett, Joseph R.
author_facet Schuster, Richard
Hanson, Jeffrey O.
Strimas-Mackey, Matthew
Bennett, Joseph R.
author_sort Schuster, Richard
collection PubMed
description The resources available for conserving biodiversity are limited, and so protected areas need to be established in places that will achieve objectives for minimal cost. Two of the main algorithms for solving systematic conservation planning problems are Simulated Annealing (SA) and exact integer linear programing (EILP) solvers. Using a case study in BC, Canada, we compare the cost-effectiveness and processing times of SA used in Marxan versus EILP using both commercial and open-source algorithms. Plans for expanding protected area systems based on EILP algorithms were 12–30% cheaper than plans using SA, due to EILP’s ability to find optimal solutions as opposed to approximations. The best EILP solver we examined was on average 1,071 times faster than the SA algorithm tested. The performance advantages of EILP solvers were also observed when we aimed for spatially compact solutions by including a boundary penalty. One practical advantage of using EILP over SA is that the analysis does not require calibration, saving even more time. Given the performance of EILP solvers, they can be used to generate conservation plans in real-time during stakeholder meetings and can facilitate rapid sensitivity analysis, and contribute to a more transparent, inclusive, and defensible decision-making process.
format Online
Article
Text
id pubmed-7261139
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher PeerJ Inc.
record_format MEDLINE/PubMed
spelling pubmed-72611392020-06-08 Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems Schuster, Richard Hanson, Jeffrey O. Strimas-Mackey, Matthew Bennett, Joseph R. PeerJ Biodiversity The resources available for conserving biodiversity are limited, and so protected areas need to be established in places that will achieve objectives for minimal cost. Two of the main algorithms for solving systematic conservation planning problems are Simulated Annealing (SA) and exact integer linear programing (EILP) solvers. Using a case study in BC, Canada, we compare the cost-effectiveness and processing times of SA used in Marxan versus EILP using both commercial and open-source algorithms. Plans for expanding protected area systems based on EILP algorithms were 12–30% cheaper than plans using SA, due to EILP’s ability to find optimal solutions as opposed to approximations. The best EILP solver we examined was on average 1,071 times faster than the SA algorithm tested. The performance advantages of EILP solvers were also observed when we aimed for spatially compact solutions by including a boundary penalty. One practical advantage of using EILP over SA is that the analysis does not require calibration, saving even more time. Given the performance of EILP solvers, they can be used to generate conservation plans in real-time during stakeholder meetings and can facilitate rapid sensitivity analysis, and contribute to a more transparent, inclusive, and defensible decision-making process. PeerJ Inc. 2020-05-27 /pmc/articles/PMC7261139/ /pubmed/32518737 http://dx.doi.org/10.7717/peerj.9258 Text en © 2020 Schuster et al. https://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ) and either DOI or URL of the article must be cited.
spellingShingle Biodiversity
Schuster, Richard
Hanson, Jeffrey O.
Strimas-Mackey, Matthew
Bennett, Joseph R.
Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title_full Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title_fullStr Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title_full_unstemmed Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title_short Exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
title_sort exact integer linear programming solvers outperform simulated annealing for solving conservation planning problems
topic Biodiversity
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7261139/
https://www.ncbi.nlm.nih.gov/pubmed/32518737
http://dx.doi.org/10.7717/peerj.9258
work_keys_str_mv AT schusterrichard exactintegerlinearprogrammingsolversoutperformsimulatedannealingforsolvingconservationplanningproblems
AT hansonjeffreyo exactintegerlinearprogrammingsolversoutperformsimulatedannealingforsolvingconservationplanningproblems
AT strimasmackeymatthew exactintegerlinearprogrammingsolversoutperformsimulatedannealingforsolvingconservationplanningproblems
AT bennettjosephr exactintegerlinearprogrammingsolversoutperformsimulatedannealingforsolvingconservationplanningproblems