Proceedings

Fast Combinatorial Algorithm for Optimizing the Spread of Cascades

XiaoJian Wu, Daniel Sheldon, Shlomo Zilberstein

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Computational Sustainability. Pages 2655-2660.

Abstract

We address a spatial conservation planning problem in which the planner purchases a budget-constrained set of land parcels in order to maximize the expected spread of a population of an endangered species. Existing techniques based on the sample average approximation scheme and standard integer programming methods have high complexity and limited scalability. We propose a fast combinatorial optimization algorithm using Lagrangian relaxation and primal-dual techniques to solve the problem approximately. The algorithm provides a new way to address a range of conservation planning and scheduling problems. On the Red-cockaded Woodpecker data, our algorithm produces near optimal solutions and runs significantly faster than a standard mixed integer program solver. Compared with a greedy baseline, the solution quality is comparable or better, but our algorithm is 10–30 times faster. On synthetic problems that do not exhibit submodularity, our algorithm significantly outperforms the greedy baseline.

Xiaojian Wu, Daniel Sheldon, and Shlomo Zilberstein. 2015. Fast Combinatorial Algorithm for Optimizing the Spread of Cascades. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2655–2660. https://ijcai.org/proceedings/2015/376
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards