Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning

Akshat Kumar, Xiaojian Wu, and Shlomo Zilberstein. Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning. Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI), 309-315, Toronto, Canada, 2012.

Abstract

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.

Bibtex entry:

@inproceedings{KWZaaai12,
  author	= {Akshat Kumar and Xiaojian Wu and Shlomo Zilberstein},
  title		= {Lagrangian Relaxation Techniques for Scalable Spatial
                   Conservation Planning},
  booktitle     = {Proceedings of the Twenty-Sixth Conference on
		   Artificial Intelligence},
  year		= {2012},
  pages		= {309-315},
  address       = {Toronto, Canada},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KWZaaai12.html}
}

shlomo@cs.umass.edu