Stochastic Combinatorial Optimization with Applications in Graph Covering

Thesis (Ph.D.)--University of Washington, 2018We study stochastic combinatorial optimization models and propose methods for their solution. First, we consider a risk-neutral two-stage stochastic programming model for which the objective value function of the second-stage subproblems is submodular. Next, we consider risk-averse combinatorial optimization problems, where in one variant, the risk is measured with a chance constraint, and in another variant, conditional value-at-risk is used to quantify risk. We demonstrate the proposed models and methods on various graph covering problems. We provide our research scope and a review of fundamental models in Chapter 1. In Chapter 2, we introduce a new class of problems that we refer to as two-stage stochastic submodular optimization models. We propose a delayed constraint generation algorithm to find the optimal solution to this class of problems with a finite number of samples. We apply the generic model and method to stochastic influence maximization problems arising in social networks. Consider a covering problem on a random graph, where there is uncertainty on whether an arc appears in the graph. The problem aims to find a subset of nodes that reaches the largest expected number of nodes in the graph. In contrast to existing studies that involve greedy approximation algorithms with a 63% performance guarantee, our work focuses on solving the problem optimally. We show that the submodularity of the influence function can be exploited to develop strong optimality cuts that are more effective than the standard optimality cuts available in the literature. We report our computational experiments with large-scale real-world datasets for two fundamental influence maximization problems, independent cascade and linear threshold, and show that our proposed algorithm outperforms the basic greedy algorithm of Kempe et al. (2003). In Chapter 3, we investigate a class of chance-constrained combinatorial optimization problems. The chance-constrained program aims to find the minimum cost selection of a vector of binary decisions such that a desirable event occurs with a high probability. For a given decision, we assume that we have an oracle that computes the probability of a desirable event exactly. Using this oracle, we propose an exact general method for solving the chance-constrained problem. Furthermore, we show that if the chance-constrained program is solved approximately by a sampling-based approach, then the oracle can be used as a tool for checking and fixing the feasibility of the optimal solution given by this approach. We demonstrate the effectiveness of our proposed methods on a probabilistic partial set covering problem (PPSC). We give a compact mixed-integer program that solves PPSC optimally (without sampling) for a special case. For large-scale instances for which the exact methods exhibit slow convergence, we propose a sampling-based approach that exploits the submodular structure of PPSC. In particular, we introduce a new class of facet-defining inequalities for a submodular substructure of PPSC and show that a sampling-based algorithm coupled with the probability oracle solves the large-scale test instances effectively. In Chapter 4, we study a class of risk-averse submodular maximization problems that optimizes the conditional value-at-risk (CVaR) of a random objective function at a given risk level, where the random objective function is defined as a nondecreasing submodular set function. We assume that we have an oracle that computes the CVaR of the random objective function exactly. Using this oracle, we propose an exact general method for solving this problem. Furthermore, we show that the problem can be solved approximately by a sampling-based approach. We demonstrate the proposed methods on a variant of stochastic set covering problem