Informs Annual Meeting 2017

SC83

INFORMS Houston – 2017

2 - Value of Randomization in Distributionally Robust Facility Location Problems Ahmed Saif, University of Waterloo, 1095 Whetherfield St., Unit 39, London, ON, N6H0B6, Canada, ansaif1976@yahoo.com, Delage Erick We study two classical facility location problems with distributional ambiguity and provide data-driven tractable reformulations that use a finite number of sample points: An UFLP with a Wasserstein-metric-based ambiguity set and a nonlinear location-inventory problem with a moment-based ambiguity set. We also study the potential benefit of randomization in MIP problems, prove that for a minimax problem, the solution of the corresponding maximin problem provides an upper bound on the value of randomization and identify the conditions under which this bound is tight. Finally, we devise and implement an efficient column- generation algorithm for facility location problems with randomization. 3 - Robust Optimization under Endogenous Uncertainty Nikolaos Lappas, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, nlappas@andrew.cmu.edu, Anirudh Subramanyam, Chrysanthos E. Gounaris When applying Robust Optimization (RO) in settings that feature uncertainty of endogenous nature, one needs to capture functional changes in parameter correlations induced by the decision-maker’s policies as well as eradicate conservatism e ects from parameters that become irrelevant in view of the optimal decisions. To that end, we introduce generic decision-dependent polyhedral uncertainty sets, and we derive the corresponding RO counterpart models as well as discuss a number of relevant algorithmic considerations. We demonstrate the versatility of our proposed sets via a number of case studies stemming from a wide range of applications. 4 - Robust Quadratically Constrained Quadratic Programming Can Gokalp, University of Texas, Austin, TX, United States, cangokalp@utexas.edu, Grani Adiwena Hanasusanto We study robust convex QCQPs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations. The emerging convex optimization problems are NP-hard but admit a conservative SDP approximation that can be solved efficiently. We prove that this approximation is stronger than the state-of-the-art approximate S-lemma scheme and demonstrate its effectiveness on a wide spectrum of computational experiments. 382C Statistics- and Information-based Approaches to Stochastic Optimization Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Saumya Sinha, University of Washington, University of Washington, Seattle, WA, 98105, United States, saumya@uw.edu 1 - A Bayesian Risk Approach to Data-Driven Stochastic Optimization Di Wu, Georgia Institute of Technology, 1995 Defoor Ave NW, Apt C, Atlanta, GA, 30318, United States, woody10074026@gmail.com, Enlu Zhou, Helin Zhu A large class of stochastic programs involve optimizing an expectation taken with respect to some underlying distribution that is unknown in practice. When data is available, a popular way to deal with such uncertainty is via distributionally robust optimization, which usually aims to hedge against the worst case over an ambiguity set. To explore the middle ground between completely ignoring the distributional uncertainty and optimizing over the worst case, we propose a Bayesian risk approach for parametric underlying distributions, which is to optimize a risk measure taken with respect to the posterior distribution of the unknown distribution parameter. 2 - Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds SC83

3 - Robust Countable-state Markov Decision Processes Saumya Sinha, University of Washington, 5204 15th Avenue NE, Apt 101, Seattle, WA, 98105, United States, saumya@uw.edu, Archis Ghate Robust optimization is a technique used to account for parameter uncertainty in stochastic optimization and has been applied extensively to the study of Markov decision processes (MDPs). For the countable-state case, however, the existing theoretical and algorithmic results are limited. In this talk, we will discuss theory as well as convergent solution-methods for countable-state robust MDPs. 4 - Probably Approximately Correct (PAC) Selection in Simulation/Best-Arm Problems David J.Eckman, Cornell University, 118 Compton Rd, Ithaca, NY, 14850, United States, dje88@cornell.edu, Shane Henderson For the problem of selecting the best from a set of simulated alternatives, the multi-armed bandit and simulation communities concentrate on two contrasting fixed-confidence guarantees. Best-arm identification procedures often guarantee selecting a near-optimal arm, i.e., probably approximately correct (PAC) selection, while ranking-and-selection procedures commonly guarantee the probability of correct selection (PCS) under the indifference-zone formulation. We discuss why PAC selection guarantees are superior and present conditions under which procedures with PCS guarantees under the indifference-zone formulation simultaneously deliver PAC selection guarantees. Sunday Plenary GBCC- General Assembly B, Level 3 Sports Scheduling Meets Business Analytics Plenary Invited Session 1 - Sports Scheduling Meets Business Analytics Mike Trick, Carnegie Mellon University in Qatar Over the last 20 years, the ability of operations research techniques to create practical sports schedules has increased tremendously. Some of this increased ability is due to faster computers and better underlying optimization software. Increased understanding of the unique aspects of sports scheduling optimization has also played a role. This is allowing the integration of predictive and prescriptive analytics resulting in schedules that are not just playable but are also profitable. 310A Developments in Utility Theory Sponsored: Decision Analysis Sponsored Session Chair: Ying He, University of Southern Denmark, Odense, M, 5230, Denmark, yinghe@sam.sdu.dk 1 - Multiattribute Utility with Bounded Tradeoffs Ilia Tsetlin, INSEAD, 1 Ayer Rajah Avenue, Singapore, 138676, Singapore, ilia.tsetlin@insead.edu, Alfred Müller, Marco Scarsini, Robert L. Winkler Suppose that, in a multiattribute setting, more of an attribute is preferred to less and states that some of the tradeoffs are bounded - e.g., both high sales and high profit are good, and one is willing to trade a particular number of units of sales for one unit of profit. We establish the form of a multiattribute utility function satisfying pre-specified bounds on the tradeoffs. Then we relate the tradeoff bounds to other preference conditions, such as the one-switch property, preferences for combining good with bad and stochastic dominance. One relevant context is the one of time preferences, where “more is better and “earlier is better” and there is also some bound on period-to-period discount rate. Sunday, 3:10 - 4:00PM Sunday, 4:30 - 6:00PM SD01

Daniel Jiang, University of Pittsburgh, 1002 Benedum Hall, 3700 O’Hara Street, Pittsburgh, PA, 15261, United States, drjiang@pitt.edu, Lina Al-Kanj, Warren B.Powell

MCTS is a well-known strategy for solving sequential decision problems, particularly in the area of game-play AI. We propose a new technique called Primal-Dual MCTS that utilizes sampled information relaxation (Brown et. al., 2010) bounds on potential actions in order to make tree expansion decisions. The approach shows promise when used to optimize the behavior of a driver navigating a graph while operating on a ride-sharing platform.

98