Stochastic Network Design: Models and Scalable Algorithms

Many natural and social phenomena occur in networks. Examples include the spread of information, ideas, and opinions through a social network, the propagation of an infectious disease among people, and the spread of species within an interconnected habitat network. The ability to modify a phenomenon towards some desired outcomes has widely recognized benefits to our society and the economy. The outcome of a phenomenon is largely determined by the topology or properties of its underlying network. A decision maker can take management actions to modify a network and, therefore, change the outcome of the phenomenon. A management action is an activity that changes the topology or other properties of a network. For example, species that live in a small area may expand their population and gradually spread into an interconnected habitat network. However, human development of various structures such as highways and factories may destroy natural habitats or block paths connecting different habitat patches, which results in a population decline. To facilitate the dispersal of species and help the population recover, artificial corridors (e.g., a wildlife highway crossing) can be built to restore connectivity of isolated habitats, and conservation areas can be established to restore historical habitats of species, both of which are examples of management actions. The set of management actions that can be taken is restricted by a budget, so we must find cost-effective allocations of limited funding resources. In the thesis, the problem of finding the (nearly) optimal set of management actions is formulated as a discrete and stochastic optimization problem. Specifically, a general decision-making framework called stochastic network design is defined to model a broad range of similar real-world problems. The framework is defined upon a stochastic network, in which edges are either present or absent with certain probabilities. It defines several metrics to measure the outcome of the underlying phenomenon and a set of management actions that modify the network or its parameters in specific ways. The goal is to select a subset of management actions, subject to a budget constraint, to maximize a specified metric. The major contribution of the thesis is to develop scalable algorithms to find high- quality solutions for different problems within the framework. In general, these problems are NP-hard, and their objective functions are neither submodular nor super-modular. Existing algorithms, such as greedy algorithms and heuristic search algorithms, either lack theoretical guarantees or have limited scalability. In the thesis, fast approximate algorithms are developed under three different settings that are gradually more general. The most restricted setting is when a network is tree-structured. For this case, fully polynomial-time approximation schemes (FPTAS) are developed using dynamic programming algorithms and rounding techniques. A more general setting is when networks are general directed graphs. We use a sampling technique to convert the original stochastic optimization problem into a deterministic optimization problem and develop a primal-dual algorithm to solve it efficiently. In the previous two problem settings, the goal is to maximize connectivity of networks. In the most general setting, the goal is to maximize the number of nodes being connected and minimize the distance between these connected nodes. For example, we do not only want the species to reach a large number of habitat areas but also want them to be able to get there within a reasonable amount of time. The scalable algorithms for this setting combine a fast primal-dual algorithm and a sampling procedure. Three real-world problems from the areas of computational sustainability and emergency response are used to evaluate these algorithms. They are the barrier removal problem aimed to determine which instream barriers to remove to help fish access their historical habitats in a river network, the spatial conservation planning problem to determine which habitat units to set as conservation areas to encourage the dispersal of endangered species in a landscape, and the pre-disaster preparation problem aimed to minimize the disruption of emergency medical services by natural disasters. In these three problems, the developed algorithms are much more scalable than the existing state-of-the-arts and produce high-quality solutions