2016 INFORMS Annual Meeting Program

74 / 561

INFORMS Nashville – 2016
74
SC16
105A-MCC
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,
1 - New Linear Algebra Strategies For Stochastic Programming
Nai-Yuan Chiang, United Technologies Research Center, 611 Silver
Ln, East Hartford, CT, 06118, United States, ,
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, , 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,
, 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, 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,
1 - Tight Formulations For Value-at-Risk Minimization Problems
Konstantin Pavlikov, University of Florida, Gainesville, FL, 32611,
United States, , 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
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,
, 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,
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, , 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.
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,
Co-Chair: Kibaek Kim, Argonne National Laboratory,
9700 Cass Ave, Lemont, IL, 60439, United States,
1 - Updates To PIPS-SBB: Distributed-memory Structure-aware
Presolve And Cut Generation
Geoffrey Malcolm Oxberry, Lawrence Livermore National
Laboratory, Livermore, CA, United States,
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.
SC16