In this dissertation we present several structure-exploiting approaches for solving stochastic programs using a scenario-based formulation, which may come from the sample average approximation of the original stochastic program.;We first study solution approaches for the design of reliably connected networks, where a minimum cost subset of arcs is selected such that the network with random arc failures is connected with probability larger than a given threshold. We present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario. The second formulation is based on an extension of graph cuts to graphs with random arc failures. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios.;We next study the chance-constrained binary packing problem, where a subset of items is selected that maximizes the total profit so that a packing constraint is satisfied with high probability. We propose a problem formulation in its original space based on probabilistic covers. We also study how methods for lifting deterministic cover inequalities can be leveraged to perform approximate lifting of probabilistic cover inequalities. The problem can also be formulated as an integer program by introducing binary scenario variables. We derive a coefficient strengthening procedure for this formulation, and demonstrate how the scenario variables can be efficiently projected out of the linear programming relaxation. We conduct a computational study to illustrate the potential benefits of our proposed techniques on various problem classes.;Finally, we study an adaptive partition-based approach for two-stage stochastic programs with fixed recourse. We propose a finitely converging algorithm by adaptively adjusting the partition until it yields an optimal solution. A solution guided refinement strategy is developed to exploit the relaxation solution that corresponds to this partition. We show that for stochastic linear programs with simple recourse, there exists a partition of a small size that yields an optimal solution. Preliminary results show that the proposed approach is competitive with Benders decomposition for stochastic linear programs with simple recourse.
展开▼
