2016 INFORMS Annual Meeting Program

SC16

INFORMS Nashville – 2016

SC16 105A-MCC

the tightest possible M is equivalent to solving another instance of VaR minimization problem. Moreover, we propose a specialized branch-and-bound algorithm to solve the problem that dynamically updates big Ms during its execution. Computational experiments are provided and discussed. 2 - A Two-stage Stochastic Program With Joint-chance Constraints For A Hybrid Wind-conventional Generator System Bismark Singh, The University of Texas at Austin, Austin, TX, bismark.singh@utexas.edu, David Morton, Surya Santoso We consider an application of a two-stage joint chance constrained stochastic program with recourse to power generation. As a first stage decision we promise an hour-by-hour firm energy output to the system operator. The conventional generator serves as a recourse option which can be used if the uncertain wind output is not large enough. We seek to ensure that with high probability our promised energy output is met by this generator and wind combination. We computationally investigate this joint-chance constrained model with recourse, using data from Texas 3 - An Integer L-shaped Approach To A Stochastic Program With Endogenous Uncertainty And Chance-constrained Recourse Gabriel Lopez Zenarosa, Assistant Professor, University of North Carolina at Charlotte, 9201 University City Blvd., Cameron Hall 242, Charlotte, NC, 28223, United States, gzenaros@uncc.edu Oleg A. Prokopyev, Andrew J. Schaefer We present a stochastic integer program with chance-constrained recourse for the surgery scheduling and one-time rescheduling problem. Our goal is to provide an approach for creating initial surgery schedules that afford agility in day-of-surgery rescheduling so as to minimize the total expected operating-room underutilization under probabilistic overutilization constraints. We use the integer L-shaped method to iteratively refine the initial surgery schedule to enable subsequent rescheduling of surgeries under the scenarios the initial schedule induces. 4 - Solving 0-1 Semidefinite Programs For Distributionally Robust Allocation Of Surgery Blocks Yiling Zhang, University of Michigan, Ann Arbor, MI, United States, zyiling@umich.edu, Siqian Shen, Ayca Erdogan We consider surgery allocation in operating rooms (ORs) under random surgery durations. We minimize the cost of opening ORs and surgery assignments, while restricting OR overtime risk via a distributionally robust (DR) chance constraint, built on a moment-based ambiguous set. Following the conic duality, the DR chance-constrained model is equivalent to a 0-1 semidefinite program, solved by a cutting-plane algorithm. Alternatively, we optimize a less conservative 0-1 second-order conic program approximation. We test outpatient treatment instances, and compare different approaches.

Algorithms for Large-Scale Stochastic Programs Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Jikai Zou, Georgia Tech, 225 North Ave, Atlanta, GA, 30332, United States, jikai.zou@gatech.edu 1 - New Linear Algebra Strategies For Stochastic Programming Nai-Yuan Chiang, United Technologies Research Center, 611 Silver Ln, East Hartford, CT, 06118, United States, chiangn@utrc.utc.com, Yankai Cao, Victor Zavala We present a clustering-based preconditioning strategy for stochastic programs within an interior-point framework on distributed memory machines. This approach is unique in that the scenario clustering is applied at the linear solver level, not at the outer NLP level, allowing for scenario clusters to change from iteration to iteration. This approach allows one to build a small and sparse pre- conditioner with fewer clusters, and then solve the full KKT system in parallel using GMRES. We also describe the features of our implementation in C++, demonstrate that high scenario compression rates of up to 94% can be obtained, and that speedups of an order of magnitude are achievable. 2 - Optimization Driven Scenario Grouping Kevin C Ryan, Georgia Institute of Technology, Atlanta, GA, United States, kryan31@gatech.edu, Shabbir Ahmed, Santanu Subhas Dey, Deepak Rajan Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems. We develop an optimization problem that selects a set of nonanticipativity constraints to re-enforce, placing scenarios into `groups’. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present a mixed integer programming formulation. Its effectiveness is demonstrated on a set of standard test instances for two-stage 0-1 stochastic programs. The idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region. 3 - MIDAS: A Mixed Integer Dynamic Approximation Scheme Andy Philpott, University of Auckland, Auckland, New Zealand, a.philpott@auckland.ac.nz, Faisal Wahid, Frederic Bonnans Mixed Integer Dynamic Approximation Scheme (MIDAS) is a sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description of MIDAS, and illustrate it on some instances of revenue maximization problems for hydroelectricity generators. 4 - Nested Decomposition Of Multistage Stochastic Integer Programs With Binary State Variables Jikai Zou, Georgia Institute of Technology, Atlanta, GA, United States, jikai.zou@gatech.edu, Shabbir Ahmed, Andy Sun We propose a valid nested decomposition algorithm for multistage stochastic integer programming problems when the state variables are binary. We prove finite convergence of the algorithm as long as the cuts satisfy some sufficient conditions. We discuss the use of well known Benders’ and integer optimality cuts within this algorithm, and introduce new cuts derived from a reformulation of the problem where local copies of state variables are introduced. We propose a stochastic variant of this algorithm and prove its finite convergence with probability one. Numerical experiment on a large-scale generation expansion planning problem will be presented. SC17 105B-MCC Optimizing Chance-Constrained Programming Variants Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Yiling Zhang, University of Michigan, Fleming Administration Building, Ann Arbor, MI, 48109, United States, zyiling@umich.edu 1 - Tight Formulations For Value-at-Risk Minimization Problems Konstantin Pavlikov, University of Florida, Gainesville, FL, 32611, United States, kpavlikov@ufl.edu, Alexander Veremyev, Eduardo Pasiliao The problem of minimization of Value-at-Risk via MIP formulations with big M constants is considered. Special emphasis is put to setting the tightest big M for every scenario where it should be positive. We show that the problem of setting

SC18 106A-MCC HPC in Optimization 2 Invited: High Performance Computing Invited Session

Chair: Geoffrey Malcolm Oxberry, Lawrence Livermore National Laboratory, Livermore, CA, United States, goxberry@gmail.com Co-Chair: Kibaek Kim, Argonne National Laboratory, 9700 Cass Ave, Lemont, IL, 60439, United States, kimk@anl.gov 1 - Updates To PIPS-SBB: Distributed-memory Structure-aware Presolve And Cut Generation Geoffrey Malcolm Oxberry, Lawrence Livermore National Laboratory, Livermore, CA, United States, oxberry1@llnl.gov Lluis-Miquel Munguia, Cosmin G Petra, Pedro Sotorrio, Thomas Edmunds, Deepak Rajan Deterministic equivalent formulations of stochastic MIPs from applications such as unit commitment (UC) can exceed available memory on a single workstation. To overcome this issue, we have developed PIPS-SBB, a distributed-memory parallel stochastic MIP solver based on the distributed-memory parallel stochastic LP solver PIPS-S. Our initial work focused on implementing a distributed-memory B&B algorithm that parallelizes LP solves. To further improve performance, we discuss implementing structure-aware variants of presolve methods and cuts, and how these methods improve performance. Based on these results, we discuss a path forward to solving large UC problem instances.

74