Informs Annual Meeting 2017

TB01

INFORMS Houston – 2017

TA82

2 - New Solution Approaches for the Maximum-reliability Stochastic Network Interdiction Problem Eli Towle, University of Wisconsin-Madison, Madison, WI, United States, etowle@wisc.edu We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination unknown to the defender and assumed to be random. We introduce a new extensive formulation that is more compact than the existing extensive formulation. We propose a new path-based formulation of SNIP and a branch-and-cut algorithm to solve it. Computational results demonstrate that both approaches provide a significant improvement over a state-of-the-art implementation of Benders decomposition for SNIP. 3 - On Continuous Mixing Cuts for Two Stage Mean Risk Stochastic Mixed Integer Programs Hideaki Nakao, University of Michigan, Ann Arbor, MI, United States, nakaoh@umich.edu, Simge Kucukyavuz, Siqian Shen We study a class of two-stage mean-risk stochastic mixed-integer linear programs (SMILP) which involve mixed-integer variables in the first stage and continuous variables in the second stage. The objective is to minimize the weighted sum of the expected value and the conditional value-at-risk (CVaR) of a random cost function dependent on first-stage decisions and realizations of uncertain parameters. A common approach for solving the two-stage optimization problem is to apply the Benders decomposition algorithm. We show how the CVaR-based Benders cuts lead to a structure that can be used to derive continuous mixing (CMIX) cuts to tighten the relaxed master problem. 4 - Decomposition Algorithms for Two-stage Distributionally Robust Mixed Binary Programs Manish Bansal, Virginia Tech., 227 Durham Hall, 1145 Perry Street, Blacksburg, VA, 24060, United States, bansal@vt.edu, Kuo-Ling Huang, Sanjay Mehrotra We present a decomposition algorithm to solve two-stage distributionally robust mixed binary problems (TSDR-MBPs) where the random parameters follow the worst-case distribution belonging to an uncertainty set of probability distributions. We investigate conditions and families of uncertainty set for which our algorithm is finitely convergent. In addition, we present a cutting surface algorithm to solve TSDR-MBPs. We computationally evaluate the performance of our algorithms in solving distributionally robust versions of a few instances from the Stochastic Integer Programming Library, in particular stochastic server location and stochastic multiple binary knapsack problem instances. Tuesday Plenary Hilton-Ballroom of America, Level 2 Plenary Plenary: How Analytics Powers the Uber Marketplace Invited Session 1 - How Analytics Powers the Uber Marketplace Robert Phillips, Director of Data Science, Uber Technologies Uber – the leading ride-sharing company in the world – faces the challenge of efficiently managing both sides of a two-sided market in which it has no direct control over either demand or supply. The challenges include determining real- time prices for both riders and drivers, matching riders and drivers and providing signals to drivers that incentivize efficient movement. In this talk we describe how Uber uses a wide variety of approaches drawn from operations research, management science, statistics, economics and machine learning to address these challenges in a highly dynamic temporospatial marketplace. Tuesday, 9:30 - 10:30AM

382B Joint Session OPT/Practice: Optimizing Power System Operations under Uncertainty Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Bita Analui, Arizona State University, Tempe, AZ, United States, bita.analui@asu.edu 1 - Evaluating Power Plant Operation and Maintenance Policies for Concentrated Solar Power Alexander Zolan, University of Texas, Austin, TX, United States, na, Jennifer DiCarlo We simulate maintenance and component failure events (i.e., for a salt-to-heat steam exchanger, three sizes of turbines, water pumps, and a generator) in a Concentrating Solar Power plant, when provided component specifications and hourly dispatch decisions from an independent optimization model; a collection of stochastic realizations of failure, repair and maintenance events, each of which includes intervals of forced plant downtime, characterize the failure events. An iterative approach takes these as inputs to suggest an improved dispatch strategy that mitigates loss of revenue associated with expected downtime, cold starts (and, more generally, cycling), and maintenance. 2 - A Dynamic Multistage Stochastic Unit Commitment Formulation for Intraday Markets Bita Analui, AZ, United States, bita.analui@asu.edu, Anna Scaglione As net-load becomes less predictable there is a lot of pressure in changing decision models for power markets such that they account explicitly for future scenarios in making commitment decisions. This paper proposes to make commitment decisions with multiple gate closures. Our proposed model also leverages a state- space formulation for the commitment variables, through which the operational constraints of generation units participating in the market are respected. We also study the problem of constructing scenario tree approximations for both original and residual stochastic processes and evaluate our algorithms on scenario tree libraries derived from real net-load data. 3 - Condition-based Generation Maintenance and Operations Scheduling under the Uncertainty of the Unexpected Failures Beste Basciftci, Georgia Institute of Technology, Atlanta, GA, United States, beste.basciftci@gatech.edu, Shabbir Ahmed, Nagi Gebraeel In this study, our aim is to effectively model and solve the integrated condition- based maintenance and operations scheduling problem of a fleet of generators by explicitly considering the unexpected failures. We formulate this problem as a stochastic mixed-integer program and introduce a chance constraint to ensure a reliable maintenance plan. We propose a data-driven approach by explicitly considering the degradation levels of the generators within the optimization model through their estimated remaining life time distributions. Finally, we present computational experiments demonstrating the effectiveness of the proposed approach. 382C Two-stage Stochastic and Distributionally Robust MIPs: Algorithms and Applications Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Manish Bansal, Virginia Tech., Blacksburg, VA, 24060, United States, bansal@vt.edu 1 - Analysis of Power Grid Attacks Mauro Escobar, Columbia University, 502 W. 122nd St, Apt 23, New York, NY, 10027, United States, me2533@columbia.edu, Daniel Bienstock This research project focuses on power grid attacks. The problem setting is as follows: an adversary has the ability of altering the supply/demand of a set S of buses in the network and report a different angle phase of a set T of buses (containing S), while a set R of buses (disjoint of T) responds to the total supply/demand change. This study analyzes the conditions in which the adversary could report phase angles that are consistent with a network flow that satisfies branch capacities and models frequency response, while the real flow would not. So far, the analysis has consisted of DC formulated simulations using cases from ‘Matpower.’ TA83

301