Approximate Algorithms for Stochastic Network Design

1 Overview

I study the problems of optimizing a range of stochastic processes occurring in networks, such as the information spreading process in a social network [Kempe et al., 2003; Chen et al., 2010], species migration processes in landscape network [Sheldon et al., 2010; Wu et al., 2013; 2014a; 2014b], virus spreading process in human contact network. In the typical network design framework, the planner can take a set of management actions, such as adding edges, removing nodes and so on, to construct a network in order to benefit the activities occurring in the networks. The set of actions being taken is called a policy. To characterize and measure the properties of the constructed network, a function is defined to map each possible policy to a real value. The goal is to select a least costly policy so that the value of the policy is greater or equal to certain value. Well known network design problems are Steiner tree problem [Hwang et al., 1992], maximum spanning tree problem [Kruskal, 1956], survival network design [Nemhauser et al., 1993] and so on. Over the last decades, substantial research has been done on both the theoretical and algorithmic aspects of these problems [Gupta and K¨onemann, 2011]. However, the standard network design framework fails to capture certain types of practical problems in which (1) the planner can take much richer set of management actions, such as raising the probabilities of certain edge being present or select the source that triggers the stochastic process; and (2) the function that maps each policy to a real value may be defined using probability and expectation. Some of these aspects have been addressed in recent applications, such as maximizing the spread of an endangered species called Red-Cockaded Woodpecker [Sheldon et al., 2010; Kumar et al., 2012]. However, existing solution techniques are not general-purpose frameworks and cannot model a broad class of network design problems. Moreover, the existing techniques that attempt to find high quality policies such as standard mixed integer program (MIP) solver, greedy algorithms or heuristic based methods suffer from limited scalability or poor performance.

My thesis contributes to both modeling and algorithm development. My first goal is to define a unifying network design framework called stochastic network design (SND) to model a broad class of network design problems under stochas- ticity. My second goal, which is my major focus, is to design effective and scalable general-purpose approxi-

Approximate Algorithms for Stochastic Network Design

Xiaojian Wu

College of Information and Computer Sciences University of Massachusetts Amherst xiaojian@cs.umass.edu

mate algorithms to solve problems that can be formulated by the SND framework.

2 Stochastic Network Design Framework

The input is a (directed) graph G = (V, E) where V is a set of vertices and E is a set of edges. Each edge is associated with a probability puv that the edge will be present in the network. Namely, it defines a distribution of networks G′ = (V,E′ ) with E′ ⊆ E. The probability of G′ is simply equal to the product of probabilities of all edges being present or absent.

To define the management actions in my framework, I first define a set of non-overlapping domains Ξ = {χ1, χ2, ..., χ|Ξ|} with χi ⊆ E. For each domain, a finite set Aχof candidate management actions are available, each having certain cost, to change the probabilities of all edges in the domain. Namely, after taking an action a ∈ Aχ, the new probability of any edge in χ becomes pe|a. To unify notations, I let each action set to contain a zero cost "noop" action a0 represents the case that no action is taken and probabilities remains unchanged. A policy π chooses exact one action for each domain. The cost of a policy is the total cost of chosen actions. A policy defines a new stochastic network with changed probabilities on edges.

To define the objective of the optimization framework, each pair of vertices is associated with a reward rs,t that encodes the importance to connect this pair. Then, we use z(π) = ∑s,t∈V P(s ⇝ t|π)r(s, t) to measure how well the vertices in the network are connected to each other in expectation, where P(s ⇝ t|π) is the probability that s is connected to t under policy π. The decision making problem is to find a policy that maximizes z(π) subject to a budget b limiting the total cost of actions being taken, that is, the optimal policy is π∗ ∈ argmax{π|c(π)≤b} z(π). It has been shown that the problem is at least #P in general graph [Valiant, 1979], so my goal is to develop efficient approximate algorithms.

3 Approximate Algorithms Overview

So far, I created algorithms for SND problem in two aspects.

1. For tree structured networks, I created fully polynomialtime approximation schemes for SND problem under certain assumptions [Wu et al., 2014a; 2014b].

1. For networks being directed graphs, I created sampling based approximate algorithms which perform well in practice.

3.1 For Tree Structured Networks

In this case, I create FPTAS for two problems:

1. barrier removal in river network to maximize the spread of fish from a unique location, for instance the entrance of the river network, which is similar to the influence maximization problem in social network [Kempe et al., 2003] except that the actions here are to remove barriers but not select sources.
2. barrier removal to maximize the connectivity of river segments, in which the difficulty is the need to consider all pairs of vertices while optimizing the connectivity.

These two problems essentially are correlated such that I can derive FPTAS for both of them using the same techniques. The basic idea is to first create a pseudocode polynomial-time algorithm using dynamic programming technique. Then, a rounding strategy is used to convert it into an FPTAS. Theoretically, the runtime of first problem is O( n2 ϵ2 ) and of the second problem is O( n8 ϵ6 ). Empirically, two algorithms can be implemented very efficiently (especially for the second problem) which outperform the existing techniques both in solution quality and runtime.

3.2 For Directed Graphs

For directed graph, the dynamic program technique is not applicable, so we use the sample average approximation (SAA) scheme to convert the stochastic optimization problem into a discrete optimization problem and then develop efficient approximate algorithms to solve it. Previously, the SAA scheme has been used to solve a spatial conservation planning problem called Red-Cockaded Woodpecker (RCW) problem [Sheldon et al., 2010] where the management actions are to purchase land parcels or vertices in the network. I extended it to solve barrier removal problem where the actions can be taken to increase the passage probabilities of barriers [Wu et al., 2013]. However, the existings methods to solve the converted discrete optimization problem are standard integer programming solver or greedy algorithms, which either appear unscalable on large networks or perform poorly. Recently, to solve the resulted discrete problem, we develped a much faster combinatorial algorithm based on Lagrangian relaxation and primal-dual techniques. We apply the algorithm to the RCW problem and show that the algorithm produces near optimal solution efficiently.

4 FutherWork

One future work will extend my combinatorial algorithm to solve more complex problems, for example the predisaster preparation for road network. Since SAA algorithm usually requires many samples to guarantee the near optimality and the complexity of the discrete problem increases rapidly with the number of samples, another interesting futuer work is to create efficient sequential sampling algorithms, where only a few samples are used in each iteration to update the solution and eventually the solution converges to a near optimal one.