Scalable Relaxations of Sparse Packing Constraints: Optimal Biocontrol in Predator-Prey Network
Cascades represent rapid changes in networks. A cascading phenomenon of ecological and economic impact is the spread of invasive species in geographic landscapes. The most promising management strategy is often biocontrol, which entails introducing a natural predator able to control the invading population, a setting that can be treated as two interacting cascades of predator and prey populations. We formulate and study a nonlinear problem of optimal biocontrol: optimally seeding the predator cascade over time to minimize the harmful prey population. Recurring budgets, which typically face conservation organizations, naturally leads to sparse constraints which make the problem amenable to approximation algorithms. Available methods based on continuous relaxations scale poorly, to remedy this we develop a novel and scalable randomized algorithm based on a width relaxation, applicable to a broad class of combinatorial optimization problems. We evaluate our contributions in the context of biocontrol for the insect pest Hemlock Wolly Adelgid (HWA) in eastern North America. Our algorithm outperforms competing methods in terms of scalability and solution quality, and finds near optimal strategies for the control of the HWA for fine-grained networks -- an important problem in computational sustainability.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationManagementSimilar Papers 제목 키워드 기반
Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization
We propose the first general and scalable framework to design certifiable algorithms for robust geometric perception in the presence of outliers. Our first contribution is to show that estimation using common robust cost…
global-optimizationPose EstimationNear-Optimal Coalition Structures in Polynomial Time
We study the classical coalition structure generation (CSG) problem and compare the anytime behavior of three algorithmic paradigms: dynamic programming (DP), MILP branch-and-bound, and sparse relaxations based on greedy…
Sparse PCA With Multiple Components
Sparse Principal Component Analysis (sPCA) is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner.…
Dense or Sparse? Post-Packing Interconnection Analysis in FPGAs
Packing is a crucial step of FPGA design, directly impacting interconnect complexity, routing congestion, and overall performance. This paper presents a post-packing interconnect-aware analysis, illustrating how dense (s…
Learning Gradient Fields for Scalable and Generalizable Irregular Packing
The packing problem, also known as cutting or nesting, has diverse applications in logistics, manufacturing, layout design, and atlas generation. It involves arranging irregularly shaped pieces to minimize waste while av…
Collision AvoidanceLayout DesignRelation Extraction