Xiaojian Wu

AAAI Conference 2018 Conference Paper

Efficiently Approximating the Pareto Frontier: Hydropower Dam Placement in the Amazon Basin

• Xiaojian Wu
• Jonathan Gomes-Selman
• Qinru Shi
• Yexiang Xue
• Roosevelt Garcia-Villacorta
• Elizabeth Anderson
• Suresh Sethi
• Scott Steinschneider

Real–world problems are often not fully characterized by a single optimal solution, as they frequently involve multiple competing objectives; it is therefore important to identify the so-called Pareto frontier, which captures solution trade-offs. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing a polynomially succinct curve that approximates the Pareto frontier to within an arbitrarily small > 0 on treestructured networks. Given a set of objectives, our approximation scheme runs in time polynomial in the size of the instance and 1/. We also propose a Mixed Integer Programming (MIP) scheme to approximate the Pareto frontier. The DP and MIP Pareto frontier approaches have complementary strengths and are surprisingly effective. We provide empirical results showing that our methods outperform other approaches in efficiency and accuracy. Our work is motivated by a problem in computational sustainability concerning the proliferation of hydropower dams throughout the Amazon basin. Our goal is to support decision-makers in evaluating impacted ecosystem services on the full scale of the Amazon basin. Our work is general and can be applied to approximate the Pareto frontier of a variety of multiobjective problems on tree-structured networks.

AAAI Conference 2018 Conference Paper

Scalable Relaxations of Sparse Packing Constraints: Optimal Biocontrol in Predator-Prey Networks

• Johan Bjorck
• Yiwei Bai
• Xiaojian Wu
• Yexiang Xue
• Mark Whitmore
• Carla Gomes

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.

AAAI Conference 2017 Conference Paper

Dynamic Optimization of Landscape Connectivity Embedding Spatial-Capture-Recapture Information

• Yexiang Xue
• Xiaojian Wu
• Dana Morin
• Bistra Dilkina
• Angela Fuller
• J. Royle
• Carla Gomes

Maintaining landscape connectivity is increasingly important in wildlife conservation, especially for species experiencing the effects of habitat loss and fragmentation. We propose a novel approach to dynamically optimize landscape connectivity. Our approach is based on a mixed integer program formulation, embedding a spatial capture-recapture model that estimates the density, space usage, and landscape connectivity for a given species. Our method takes into account the fact that local animal density and connectivity change dynamically and non-linearly with different habitat protection plans. In order to scale up our encoding, we propose a sampling scheme via random partitioning of the search space using parity functions. We show that our method scales to realworld size problems and dramatically outperforms the solution quality of an expectation maximization approach and a sample average approximation approach.

AAAI Conference 2017 Conference Paper

Robust Optimization for Tree-Structured Stochastic Network Design

• Xiaojian Wu
• Akshat Kumar
• Daniel Sheldon
• Shlomo Zilberstein

Stochastic network design is a general framework for optimizing network connectivity. It has several applications in computational sustainability including spatial conservation planning, pre-disaster network preparation, and river network optimization. A common assumption in previous work has been made that network parameters (e. g. , probability of species colonization) are precisely known, which is unrealistic in real-world settings. We therefore address the robust river network design problem where the goal is to optimize river connectivity for fish movement by removing barriers. We assume that fish passability probabilities are known only imprecisely, but are within some interval bounds. We then develop a planning approach that computes the policies with either high robust ratio or low regret. Empirically, our approach scales well to large river networks. We also provide insights into the solutions generated by our robust approach, which has significantly higher robust ratio than the baseline solution with mean parameter estimates.

IJCAI Conference 2017 Conference Paper

XOR-Sampling for Network Design with Correlated Stochastic Events

• Xiaojian Wu
• Yexiang Xue
• Bart Selman
• Carla P. Gomes

Many network optimization problems can be formulated as stochastic network design problems in which edges are present or absent stochastically. Furthermore, protective actions can guarantee that edges will remain present. We consider the problem of finding the optimal protection strategy under a budget limit in order to maximize some connectivity measurements of the network. Previous approaches rely on the assumption that edges are independent. In this paper, we consider a more realistic setting where multiple edges are not independent due to natural disasters or regional events that make the states of multiple edges stochastically correlated. We use Markov Random Fields to model the correlation and define a new stochastic network design framework. We provide a novel algorithm based on Sample Average Approximation (SAA) coupled with a Gibbs or XOR sampler. The experimental results on real road network data show that the policies produced by SAA with the XOR sampler have higher quality and lower variance compared to SAA with Gibbs sampler.

AAAI Conference 2016 Conference Paper

Optimizing Resilience in Large Scale Networks

• Xiaojian Wu
• Daniel Sheldon
• Shlomo Zilberstein

We propose a decision making framework to optimize the resilience of road networks to natural disasters such as floods. Our model generalizes an existing one for this problem by allowing roads with a broad class of stochastic delay models. We then present a fast algorithm based on the sample average approximation (SAA) method and network design techniques to solve this problem approximately. On a small existing benchmark, our algorithm produces near-optimal solutions and the SAA method converges quickly with a small number of samples. We then apply our algorithm to a large real-world problem to optimize the resilience of a road network to failures of stream crossing structures to minimize travel times of emergency medical service vehicles. On medium-sized networks, our algorithm obtains solutions of comparable quality to a greedy baseline method but is 30–60 times faster. Our algorithm is the only existing algorithm that can scale to the full network, which has many thousands of edges.

IJCAI Conference 2015 Conference Paper

Approximate Algorithms for Stochastic Network Design

• Xiaojian Wu

IJCAI Conference 2015 Conference Paper

Fast Combinatorial Algorithm for Optimizing the Spread of Cascades

• Xiaojian Wu
• Daniel Sheldon
• Shlomo Zilberstein

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.

UAI Conference 2015 Conference Paper

Optimal Threshold Control for Energy Arbitrage with Degradable Battery Storage

• Marek Petrik
• Xiaojian Wu

Energy arbitrage has the potential to make electric grids more efficient and reliable. Batteries hold great promise for energy storage in arbitrage but can degrade rapidly with use. In this paper, we analyze the impact of storage degradation on the structure of optimal policies in energy arbitrage. We derive properties of the battery degradation response that are sufficient for the existence of optimal threshold policies, which are easy to interpret and compute. Our experimental results suggest that explicitly considering battery degradation in optimizing energy arbitrage significantly improves solution quality.

AAAI Conference 2014 Conference Paper

Optimizing and Learning Diffusion Behaviors in Complex Network

• Xiaojian Wu

AAAI Conference 2014 Conference Paper

Rounded Dynamic Programming for Tree-Structured Stochastic Network Design

• Xiaojian Wu
• Daniel Sheldon
• Shlomo Zilberstein

We develop a fast approximation algorithm called rounded dynamic programming (RDP) for stochastic network design problems on directed trees. The underlying model describes phenomena that spread away from the root of a tree, for example, the spread of influence in a hierarchical organization or fish in a river network. Actions can be taken to intervene in the network—for some cost—to increase the probability of propagation along an edge. Our algorithm selects a set of actions to maximize the overall spread in the network under a limited budget. We prove that the algorithm is a fully polynomial-time approximation scheme (FPTAS), that is, it finds (1 ✏)-optimal solutions in time polynomial in the input size and 1/✏. We apply the algorithm to the problem of allocating funds efficiently to remove barriers in a river network so fish can reach greater portions of their native range. Our experiments show that the algorithm is able to produce nearoptimal solutions much faster than an existing technique.

NeurIPS Conference 2014 Conference Paper

Stochastic Network Design in Bidirected Trees

• Xiaojian Wu
• Daniel Sheldon
• Shlomo Zilberstein

We investigate the problem of stochastic network design in bidirected trees. In this problem, an underlying phenomenon (e. g. , a behavior, rumor, or disease) starts at multiple sources in a tree and spreads in both directions along its edges. Actions can be taken to increase the probability of propagation on edges, and the goal is to maximize the total amount of spread away from all sources. Our main result is a rounded dynamic programming approach that leads to a fully polynomial-time approximation scheme (FPTAS), that is, an algorithm that can find (1−ε)-optimal solutions for any problem instance in time polynomial in the input size and 1/ε. Our algorithm outperforms competing approaches on a motivating problem from computational sustainability to remove barriers in river networks to restore the health of aquatic ecosystems.

IJCAI Conference 2013 Conference Paper

Parameter Learning for Latent Network Diffusion

• Xiaojian Wu
• Akshat Kumar
• Daniel Sheldon
• Shlomo Zilberstein

Diffusion processes in networks are increasingly used to model dynamic phenomena such as the spread of information, wildlife, or social influence. Our work addresses the problem of learning the underlying parameters that govern such a diffusion process by observing the time at which nodes become active. A key advantage of our approach is that, unlike previous work, it can tolerate missing observations for some nodes in the diffusion process. Having incomplete observations is characteristic of offline networks used to model the spread of wildlife. We develop an EM algorithm to address parameter learning in such settings. Since both the E and M steps are computationally challenging, we employ a number of optimization methods such as nonlinear and difference-of-convex programming to address these challenges. Evaluation of the approach on the Red-cockaded Woodpecker conservation problem shows that it is highly robust and accurately learns parameters in various settings, even with more than 80% missing data.

AAAI Conference 2012 Conference Paper

Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning

• Akshat Kumar
• Xiaojian Wu
• Shlomo Zilberstein

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.

IJCAI Conference 2011 Conference Paper

Learning Optimal Bayesian Networks Using A* Search

• Changhe Yuan
• Brandon Malone
• Xiaojian Wu

This paper formulates learning optimal Bayesian network as a shortest path finding problem. An A* search algorithm is introduced to solve the problem. With the guidance of a consistent heuristic, the algorithm learns an optimal Bayesian networkby only searching the most promising parts of the solution space. Empirical results show that the A*search algorithm significantly improves the time and space efficiency of existing methods on a set of benchmark datasets.

UAI Conference 2010 Conference Paper

Solving Multistage Influence Diagrams using Branch-and-Bound Search

• Changhe Yuan
• Xiaojian Wu
• Eric A. Hansen

A branch-and-bound approach to solving influence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated – apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementation of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.