Fast Combinatorial Algorithm for Optimizing the Spread of Cascades

Xiaojian Wu, Daniel Sheldon, and Shlomo Zilberstein. Fast Combinatorial Algorithm for Optimizing the Spread of Cascades. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI), 2655-2661, Buenos Aires, Argentina, 2015.

Abstract

We address a spatial conservation planning prob- lem 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.

Bibtex entry:

@inproceedings{WSZijcai15,
  author	= {Xiaojian Wu and Daniel Sheldon and Shlomo Zilberstein},
  title		= {Fast Combinatorial Algorithm for Optimizing the Spread of Cascades},
  booktitle     = {Proceedings of the Twenty-Fourth International Joint Conference on
                   Artificial Intelligence},
  year		= {2015},
  pages		= {2655-2661},
  address       = {Buenos Aires, Argentina},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WSZijcai15.html}
}

shlomo@cs.umass.edu