2016 INFORMS Annual Meeting Program

23 / 561

INFORMS Nashville – 2016
23
SA19
3 - Dueling Bandits With Dependent Arms
Bangrui Chen, Cornell University,
We consider online content recommendation with implicit feedback through
pairwise comparisons. We study a new formulation of the dueling bandit
problems in which arms are dependent and regret occurs when neither pulled
arm is optimal. We propose a new algorithm, Comparing The Best (CTB),
appropriate for problems with few arms, and a variation of this algorithm for
problems with many arms. We show both algorithms have constant expected
cumulative regret. We demonstrate through numerical experiments on simulated
and real dataset that these algorithms improve significantly over existing
algorithms in the setting we study.
4 - Asymptotic Optimality In Finite Horizon Multi-armed Bandits With
Multiple Pulls Per Period
Weici Hu, Cornell University (ORIE),
We view the finite horizon multi-arm bandit problem with multiple pulls per
period (MABMP) as a special case of a weakly coupled dynamic program
(WCDP). A WCDP is a class of optimal control problems for which the complexity
can be reduced by Lagrangian Relaxation. We propose an index-based policy that
utilizes the Lagrange multiplier in the relaxed problem, and give a proof that this
index-based policy is asymptotically close to the optimal policy as the problem
size gets larger. We also use simulation to show that this index policy performs
better than state-of-art heuristics in various problem sizes.
SA18
106A-MCC
High-Performance Computing for
Stochastic Optimization
Invited: High Performance Computing
Invited Session
Chair: Jean-Paul Watson, Sandia National Laboratories, P.O. Box 5800,
MS 1326, Albuquerque, NM, 87185, United States,
1 - Parallel Branch-and-bound Based On PH For Stochastic MIPS
David Woodruff, University of California Davis,
, Jason Barnett
Progressive hedging (PH), though an effective heuristic for stochastic
mixed integer programs (MIPs), is not guaranteed convergence in the
integer case. Here, we describe BBPH, a branch and bound algorithm that uses PH
within each node that, given enough time, will always converge to the optimal
solution. In addition to providing a theoretically convergent wrapper for PH
applied to MIPs, computational results are given that demonstrate that for some
difficult problem instances branch and bound can find improved solutions within
a few branches.
2 - Schuripopt: A Parallel Optimization Package For Structured
Nonlinear-programming Problems
Gabriel Hackebeil, University of Michigan, Ann Arbor, MI,
United States, Jose Santiago Rodriguez,
Jean-Paul Watson, Carl Laird
In this work, we develop SchurIpopt, a parallel extension to Ipopt that solves
structured NLP problems efficiently on shared memory and distributed memory
parallel architectures. Our implementation uses a Schur-complement
decomposition strategy to exploit the structure of NLP problems arising in multi-
scenario and dynamic optimization applications. The implementation achieves
high parallel efficiency by parallelizing the solution of the KKT system and related
vector-vector and matrix-vector operations. We interface SchurIpopt with PySP —
a Python-based software package for modeling stochastic programming problems,
which is an extension of the open-source AML Pyomo .
3 - Parallel Solution Of Large-scale Stochastic Economic Dispatch
And Unit Commitment Problems
Jean-Paul Watson, Sandia National Laboratories,
We consider the solution of large-scale, industrially relevant economic dispatch
and unit commitment problems, for systems with large renewables penetration
levels, using parallel scenario-based decomposition methods. We discuss both
lower and upper bounding performance, in the context of CAISO and other
realistic data sets. We will detail tuning and implementation issues that impact
and in some cases limit scalability of scenario-based decomposition (in particular,
progressive hedging) on these problems.
SA19
106B-MCC
Computing
Sponsored: Computing
Sponsored Session
Chair: Guzin Bayraksan, The Ohio State University, The Ohio State
University, Columbus, OH, United States,
1 - Reconfigurable Optimization
Prateek Raj Srivastava, Graduate Research Assistant,
The University of Texas at Austin, 204 East Dean Keeton Street,
Engineering Training Center II (ETC), Austin, TX, 78712,
United States, , Nedialko Dimitrov,
David L. Alderson
We develop a modeling framework for a class of optimization problems in which
operational decisions need to be altered as a system transitions stochastically
between states of the world. Our framework addresses the multi-objective
problem of minimizing reconfiguration costs associated with changing the
operational decisions and ensuring good quality solutions in each individual state.
We compare and contrast our model solutions with those obtained from other
modeling frameworks like Stochastic and Robust Optimization.
2 - Variance Reduction For Sequential Sampling In
Stochastic Optimization
Jangho Park, The Ohio State University, Columbus, OH, United
States, Rebecca Stockbridge, Güzin Bayraksan
We investigate Antithetic Variates (AV) and Latin Hypercube Sampling (LHS) for
sequential sampling in stochastic optimization. We assume a sequence of
solutions is given and employ AV or LHS to assess the quality of these solutions in
a sequential sampling framework. The sequence of solutions can be given by any
method satisfying some convergence properties. Therefore, the sequential
framework can be used by a variety of methods to find high-quality solutions
with a desired probability. We present theoretical justification and update the
theory especially for LHS. Computational results indicate that the use of AV and
LHS can lead to tighter confidence intervals on the quality of solutions obtained.
3 - A Tractable Stochastic Program For The Operation Of A
Hydroelectrical Complex With Uncertain Inflows
Charles Gauvin, École Polytechnique de Montréal, 2900 Boul.
Édouard-Montpetit, Montréal, QC, H3T 1J4, Canada,
, Erick Delage, Michel Gendreau
This talk considers the operation of a real multireservoir hydroelectrical complex.
We focus on the uncertainty surrounding inflows and explicitly capture the serial
correlation though well-known time series. We then consider affine decision rules
to quickly obtain solutions to this multistage stochastic program. Finally, we
evaluate the quality of these policies by embedding our approach into a rolling
horizon simulation.
4 - Distributionally Robust Newsvendor Problem With
Variation Distance
Hamed Rahimian, PhD Candidate, The Ohio State University,
1971 Neil Ave., Columbus, OH, 43215, United States,
, Guzin Bayraksan, Tito Homem-de-Mello
We study a general class of newsvendor models where the underlying demand
distribution is unknown. An ambiguity set of distributions is formed by the
variation distance centered around a nominal continuous distribution. We
characterize the optimal solution to the resulting distributionally robust problem.
Then, we examine which demand levels are more critical to the optimal cost than
others. Finally, we show the sets of critical demands are decreasing and converge
to a set of measure zero as the level of robustness increases. Numerical results
show that the optimal decision to the risk-neutral model plays an important role
to characterize the most critical demands.