Optimal Network Design for the Spread of Cascades
MetadataShow full item record
Sheldon, Daniel; Dilkina, Bistra; Elmachtoub, Adam; Finseth, Ryan; Sabharwal, Ashish; Conrad, Jon; Gomes, Carla P.; Shmoys, David; Allen, Will; Amundsen, Ole; Vaughan, Buck
We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dynamics by adding nodes or edges to the network. Our motivating application is one in spatial conservation planning, where a cascade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formulation that combines elements from network design and stochastic optimization. Our approach, evaluated on data obtained from a red-cockaded woodpecker (RCW) conservation effort in southeastern United States, results in solutions with stochastic optimality guarantees and points to conservation strategies that are fundamentally different from naive approaches.
computational sustainability; diffusion in networks; conservation planning; red-cockaded woodpecker; RCW; social networks; mixed-integer programming; sample average approximation; optimization