2016 INFORMS Annual Meeting Program

SA19

INFORMS Nashville – 2016

SA19 106B-MCC Computing Sponsored: Computing Sponsored Session

3 - Dueling Bandits With Dependent Arms Bangrui Chen, Cornell University, bc496@cornell.edu

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), wh343@cornell.edu 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.

Chair: Guzin Bayraksan, The Ohio State University, The Ohio State University, Columbus, OH, United States, bayraksan.1@osu.edu

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, prateekrs@utexas.edu, 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

SA18 106A-MCC High-Performance Computing for Stochastic Optimization Invited: High Performance Computing Invited Session

Jangho Park, The Ohio State University, Columbus, OH, United States, park.1814@osu.edu, 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, charles.gauvin@polymtl.ca, 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, rahimian.1@osu.edu, 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.

Chair: Jean-Paul Watson, Sandia National Laboratories, P.O. Box 5800, MS 1326, Albuquerque, NM, 87185, United States, jwatson@sandia.gov 1 - Parallel Branch-and-bound Based On PH For Stochastic MIPS David Woodruff, University of California Davis, dlwoodruff@ucdavis.edu, 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, hackebeg@umich.edu, 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 (pyomo.org). 3 - Parallel Solution Of Large-scale Stochastic Economic Dispatch And Unit Commitment Problems Jean-Paul Watson, Sandia National Laboratories, jwatson@sandia.gov 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.

23