Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning
We address the problem of spatial conservation planning in which the goal is to maximize the expected spread of cascades of an endangered species by strategically purchasing land parcels within a given budget. This problem can be solved by standard integer programming methods using the sample averag...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2012
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/2202 https://ink.library.smu.edu.sg/context/sis_research/article/3202/viewcontent/Lagrangian_Relaxation_Techniques_for_Scalable_Spatial.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-3202 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-32022018-07-13T03:44:28Z Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning KUMAR, Akshat WU, Xiaojian ZILBERSTEIN, Shlomo We address the problem of spatial conservation planning in which the goal is to maximize the expected spread of cascades of an endangered species by strategically purchasing land parcels within a given budget. This problem can be solved by standard integer programming methods using the sample average approximation (SAA) scheme. Our main contribution lies in exploiting the separable structure present in this problem and using Lagrangian relaxation techniques to gain scalability over the flat representation. We also generalize the approach to allow the application of the SAA scheme to a range of stochastic optimization problems. Our iterative approach is highly efficient in terms of space requirements and it provides an upper bound over the optimal solution at each iteration. We apply our approach to the Red-cockaded Woodpecker conservation problem. The results show that it can find the optimal solution significantly faster -- sometimes by an order-of-magnitude -- than using the flat representation for a range of budget sizes. 2012-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/2202 https://ink.library.smu.edu.sg/context/sis_research/article/3202/viewcontent/Lagrangian_Relaxation_Techniques_for_Scalable_Spatial.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Artificial Intelligence and Robotics Computer Sciences |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Artificial Intelligence and Robotics Computer Sciences |
spellingShingle |
Artificial Intelligence and Robotics Computer Sciences KUMAR, Akshat WU, Xiaojian ZILBERSTEIN, Shlomo Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
description |
We address the problem of spatial conservation planning in which the goal is to maximize the expected spread of cascades of an endangered species by strategically purchasing land parcels within a given budget. This problem can be solved by standard integer programming methods using the sample average approximation (SAA) scheme. Our main contribution lies in exploiting the separable structure present in this problem and using Lagrangian relaxation techniques to gain scalability over the flat representation. We also generalize the approach to allow the application of the SAA scheme to a range of stochastic optimization problems. Our iterative approach is highly efficient in terms of space requirements and it provides an upper bound over the optimal solution at each iteration. We apply our approach to the Red-cockaded Woodpecker conservation problem. The results show that it can find the optimal solution significantly faster -- sometimes by an order-of-magnitude -- than using the flat representation for a range of budget sizes. |
format |
text |
author |
KUMAR, Akshat WU, Xiaojian ZILBERSTEIN, Shlomo |
author_facet |
KUMAR, Akshat WU, Xiaojian ZILBERSTEIN, Shlomo |
author_sort |
KUMAR, Akshat |
title |
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
title_short |
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
title_full |
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
title_fullStr |
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
title_full_unstemmed |
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning |
title_sort |
lagrangian relaxation techniques for scalable spatial conservation planning |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2012 |
url |
https://ink.library.smu.edu.sg/sis_research/2202 https://ink.library.smu.edu.sg/context/sis_research/article/3202/viewcontent/Lagrangian_Relaxation_Techniques_for_Scalable_Spatial.pdf |
_version_ |
1770571882281566208 |