Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SC73

3 - Parallel Temporal Decomposition Method for Long-term Unit Commitment Problems Kibaek Kim, Argonne National Laboratory, 9700 South Cass Avenue, Building 240, Lemont, IL, 60439, United States, Audun Botterud, Feng Qiu We consider a long-term unit commitment (UC) for power system production cost modeling. The UC problem is formulated as a large-scale mixed-binary linear programming problem. We present the Lagrangian dual decomposition method that solves the long-term UC by decoupling the long-term horizon into several sub-horizons. We also develop the branch-and-bound method on top of the dual decomposition, which enables to find a global optimal solution. The method has been implemented in an open-source optimization framework DSP that can run in parallel on high-performance computing clusters. In our computational experiments, we show significant reductions in solution time as compared with CPLEX. 4 - ADMM for SCUC: Effects of Market Characteristics and Subproblem Design on Algorithm Performance Jesse Holzer, Pacific Northwest National Laboratory, 902 Battelle Blvd, Richland, WA, 99354, United States, Feng Pan, Yonghong Chen, Stephen Elbert Security constrained unit commitment (SCUC) is the computational engine for day ahead wholesale electricity markets. As markets evolve, larger networks and numerous smaller energy resources pose increasing computational challenges for mixed integer programming (MIP) solvers. The alternating direction method of multipliers (ADMM) has been applied to SCUC as a scalable alternative to MIP. ADMM has guaranteed convergence in convex problems, but SCUC is nonconvex. We compare ADMM and MIP on large scale instances, observing that smaller and more numerous resources and larger subsystems tend to improve ADMM convergence but make the subproblems more expensive. Nicholson Student Paper Competition II Emerging Topic: Nicholson Student Paper Prize Emerging Topic Session Chair: John Hasenbein, University of Texas-Austin, 1 University Station Stop C2200, Department of Mechanical Engineering, Austin, TX, 78712-0292, United States Chair: Phebe Vayanos, University of Southern California, OHE 310L, University Park Campus, USC, Viterbi School of Engineering, Los Angeles, CA, 90089, United States 1 - Synthesis and Generalization of Structural Results in Inventory Management: A Generalized Convexity Property Zhe Liu, Columbia University, New York, NY, USA, Awi Federgruen We address a general periodic review inventory control model with the simultaneous presence of the following complications: (a) bilateral inventory adjustment options, via procurement orders and salvage sales or returns to the supplier; (b) fixed costs associated with procurement orders and downward inventory adjustments (via salvage sales or returns); and (c) capacity limits associated with upward or downward inventory adjustments. We provide a full characterization of the optimal procurement strategy, both for finite and infinite horizon periodic review models, by showing that in each period the inventory position line is to be partitioned into (maximally) five regions. Our results are obtained by identifying a novel generalized convexity property for the value functions, which we refer to as strong (C1K1,C2K2)-convexity. To our knowledge, we recover almost all existing structural results for models with exogenous demands as special cases of a unified analysis. 2 - Small-loss Bounds for Online Learning with Partial Information Thodoris Lykouris. Cornell University, Ithaca, NY, USA. We consider the problem of adversarial (non-stochastic) online learning with partial information feedback, where at each round, a decision maker selects an action from a finite set of alternatives. We develop a black-box approach for such problems where the learner observes as feedback only losses of a subset of the actions that includes the selected action. When losses of actions are non-negative, under the graph-based feedback model introduced by Mannor and Shamir, we o er algorithms that attain the so called “small-loss” o( L?) regret bounds with high probability, where is the independence number of the graph, and L? is the loss of the best action. Prior to our work, there was no data-dependent guarantee for general feedback graphs even for pseudo-regret (without dependence on the number of actions, i.e. utilizing the increased information feedback). Taking advantage of the black-box nature of our technique, we extend our results to many other applications such as semi-bandits (including routing in networks), n SC72 West Bldg 211A

contextual bandits (even with an infinite comparator class), as well as learning with slowly changing comparators. In the special case of classical bandit and semi- bandit problems, we provide optimal small-loss, high-probability guarantees of e O( √ dL?) for actual regret, where d is the number of actions, answering open questions of Neu. Previous bounds for bandits and semi-bandits were known only for pseudo-regret and only in expectation. We also o er an optimal e O( √ L?) regret guarantee for fixed feedback graphs with clique-partition number at most . 3 - Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator Daniel Kuhn, Ecole Polytechnique Federale de Lausanne (EPFL), Lausanne, Switzerland, Viet Anh Nguyen. We introduce a distributionally robust maximum likelihood estimation model with a Wasserstein ambiguity set to infer the inverse covariance matrix of a p- dimensional Gaussian random vector from n independent samples. The proposed model minimizes the worst case (maximum) of Stein’s loss across all normal reference distributions within a prescribed Wasserstein distance from the normal distribution characterized by the sample mean and the sample covariance matrix. We prove that this estimation problem is equivalent to a semidefinite program that is tractable in theory but beyond the reach of general purpose solvers for practically relevant problem dimensions p. In the absence of any prior structural information, the estimation problem has an analytical solution that is naturally interpreted as a nonlinear shrinkage estimator. Besides being invertible and well conditioned even for p > n, the new shrinkage estimator is rotation-equivariant and preserves the order of the eigenvalues of the sample covariance matrix. These desirable properties are not imposed ad hoc but emerge naturally from the underlying distributionally robust optimization model. 4 - Data-Driven Personalized Decision Making: Algorithm, Theory and Application Zhengyuan Zhou, Stanford University, Stanford, CA, USA. In this paper, we study the general o ine policy learning problem where we aim to learn an e ective policy from observational datasets. We propose a novel learning algorithm and establish that it achieves the (asymptotically) optimal regret guarantee, there by settling the open problem of which learning algorithm to choose in this context. To the best of our knowledge, this is the first provably optimal learning algorithmin the general o ine policy earning problem and provides a substantial performance improvement over all the exisiting learning algorithms. We also additionally investigate the application aspects of policy learning by working with finite-depth trees, a specific policy class that is widely used as decision rules in practice. We formulate a key step of the learning algorithm as a mixed integer program, which enables us to solve it to exact optimality. Together, these results contribute to the broad landscape of data science by providing a state-of-the-art personalized decision making framework that is optimal in both generalization and optimization. JFIG Paper Competition II Sponsored: Junior Faculty JFIG Sponsored Session Chair: Oleg Prokopyev, University of Pittsburgh, 1031 Benedum Hall, Pittsburgh, PA, 15261, United States Co-Chair: Fatma Kilinc Karzan, Carnegie Mellon University, Pittsburgh, PA, 15217, United States 1- JFIG Paper Competition Oleg Prokopyev, University of Pittsburgh, Pittsburgh, PA, USA, The 2018 JFIG paper competition features paper submissions from a diverse array of talented junior faculty members. The prize committee evaluated submissions based on the importance of the topic, appropriateness of the approach, and significance of the contribution. After careful review, the prize committee selected a group of finalists to present their research in one of the two JFIG sessions. For information on the finalists and their papers, please refer to the online program.. n SC73 West Bldg 211B

87