Informs Annual Meeting 2017

SA77

INFORMS Houston – 2017

3 - Computer-assisted Discovery and Certification of Next-generation Cutting Planes for Mixed Integer Programming Matthias Koeppe, University of California-Davis, One Shields Avenue, Dept of Mathematics, Davis, CA, 95616, United States, mkoeppe@math.ucdavis.edu, Yuan Zhou The revival of Gomory’s classic general purpose cutting planes in the mid-1990s enabled the development of powerful branch-and-cut software. Challenging new applications and increased data sizes prompt us to develop next-generation general-purpose cutting plane systems. We revisit Gomory and Johnson’s infinite- dimensional relaxations of integer programs. We overcome the difficulties in studying the “facet-defining” valid inequalities of these relaxations by making use of computer-assisted discovery and certification. The goal is to develop a large library of parametric families of such “facets” as the foundation of learning-based cutting-plane systems. 4 - Cutting Planes from Extended Formulations Sanjeeb Dash, IBM T.J.Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY, 10598, United States, sanjeebd@us.ibm.com We discuss how to use extended formulations of the LP relaxation of a mixed- integer program to obtain stronger split cutting planes than those that can be obtained from the original LP relaxation. We analyze a few different approaches to building extended formulations, and the effectiveness of split cuts in each case. In particular, we consider the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies, and also discuss extended formulations of mixed-integer programs obtained by replacing integral variables by weighted sums of binary variables. 372F Dynamic Optimization for Allocation Problems Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Viswanath Nagarajan, University of Michigan, Ann Arbor, MI, 48109, United States, viswa@umich.edu 1 - Pricing in Dynamic Two-sided Markets with Service Guarantees Kamesh Munagala, Professor, Duke University, P.O. Box 90129, Department of Computer Science, Durham, NC, 27708-0129, United States, kamesh@cs.duke.edu, Reza Alijani, Siddhartha Banerjee, Sreenivas Gollapudi, Konstantinos Kollias We consider dynamic two-sided markets, where buyers and sellers arrive over time following Poisson processes. Each agent has private value and patience level for receiving/providing service, and a known location in an underlying metric space. The platform posts prices and wages at nodes in the metric space, as well as choose agents for matching to simultaneously ensure three orthogonal objectives: 1) maximizing profit; 2) minimizing maximum metric distance of any match; and 3) minimizing abandonment probability of an accepted agent. We consider a natural class of scheduling policies, and develop LP rounding techniques that find approximately optimal policies. 2 - Exact Competitive Ratios for Online Edge-weighted Bipartite Matching with a Known Set of Edge Weights Will Ma, Massachusetts Institute of Technology, 71 School Street, Cambridge, MA, 02139, United States, willma353@gmail.com, David Simchi-Levi In this paper we obtain tight competitive ratios for the online edge-weighted bipartite matching problem, as a function of the set of potential edge weights, which is assumed to be given in advance. We obtain corresponding results for the Adwords problem under the small bids assumption, and the stochastic matching setting if each fixed node can be matched a large number of times. Our results are for the adversarial arrival model, and based on our optimal “tradeoff function” for online budgeted allocation in general, when each budget, or resource, could be converted to reward at multiple rates. Our analysis is primal-dual, and uses a randomly-initialized tradeoff function to handle the multiple rates. 3 - Closing the Gaps: An Online Learning Algorithm for the Lost-sales Inventory System with Lead Times Huanan Zhang, University of Michigan, 2133 Glencoe Hills Drive, Apt 10, Ann Arbor, MI, 48108-1094, United States, zhanghn@umich.edu, Xiuli Chao, Cong Shi We develop an improved nonparametric learning algorithm for periodic-review lost sales inventory systems with positive lead time, where the firm does not know the demand distribution a priori but makes the replenishment decision in each period based only on the past sales (censored demand) data. It is known that the optimal policy is hard to compute even with full information, hence in this paper we focus on finding the best base-stock policy. We establish a square-root convergence rate of the proposed learning algorithm, which is the best possible rate for this class of problems. SA77

4 - Adaptivity Gaps for Stochastic Probing Problems Viswanath Nagarajan, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109, United States, viswa@umich.edu, Anupam Gupta, Sahil Singla We consider a general class of stochastic probing problems with submodular or subadditive objectives. Each element is active independently with some known probability, but we know the status of an element only after “probing” it. There is also a constraint on the sequence of elements that may be probed. The goal is to find a policy for probing elements so as to maximize the expected function value on the active elements. Such problems arise in many applications, eg. influence maximization, Bayesian mechanism design and path planning. We show that the gap between optimal adaptive and non-adaptive policies is small, which also leads to good approximation algorithms for these stochastic probing problems. 380B Energy Contributed Session Chair: Emre Çelebi, Kadir Has University, Istanbul, Turkey, ecelebi@khas.edu.tr 1 - Efficient Allocation of Benefits in Multinational Transmission Expansion Planning using Cooperative Game Theory Martin Kristiansen, PhD Student, NTNU, Nedre Mollenberg gate 23A, Trondheim, 7014, Norway, martin.kristiansen@ntnu.no There are multiple countries involved in, or affected by, multinational grid investments. Although cooperative investment strategies always result in nonnegative aggregate net-benefits, benefits for individual parties can be asymmetric and, in some cases, negative. In this talk, we present a methodology to determine an efficient and fair allocation of benefits using Shapley Value from cooperative game theory. Moreover, we verify numerically that our case study of the North Sea Offshore Grid yields a convex cooperative game, meaning that the computed allocation is in the core and, consequently, provides a higher payoff to all countries than under any other possible subcoalition. 2 - Enhanced Representative Days and System States Modeling for Energy Storage Investment Diego Alejandro Tejada Arango, Research Assistant, Universidad Pontificia Comillas, C/ Santa Cruz de Marcenado 26, Madrid, 28015, Spain, dtejada@comillas.edu, Sonja Wogrin, Efraim Centeno In this work, we analyze the impact of different options to represent the operation decisions in the study of energy storage (ES) investment for long-term planning models. We compare the representative days and the system-states approaches for the representation of these operation decisions. We proposed enhanced versions of these approaches to improve the ES investment approximation. An Spanish case study is evaluated and the results are used to identify the potential profits that energy storage investment can obtain. 3 - Investment Plan Against Malicious Attacks on Power Networks: Multilevel Game-theoretic Models with Shared Cognition Hamzeh Davarikia, PhD Candidate, Research Assistant, University of Arkansas, 2801 S.University Avenue, Little Rock, AR, 72204, United States, hxdavarikia@ualr.edu, Mustafa Alassad, Yupo Chan We developed a tool for utility transmission planners to protect power network from potential attacks. An extended tri-level mixed-integer linear-programming interdiction-model returns the best protecting strategy. Deception is an integral part of the mathematical model, accomplished by releasing misinformation based on shared cognition theory. In addition, the multi origin-destination model allows the impact of disabled facilities to become transparent. The results from IEEE 24 and 118 Bus Test Systems show the viability of the model, including its capacity to impute the worth of deception. 4 - Nested Decomposition Algorithm for Electric Power Infrastructure Planning Cristiana Lara, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, cristianallara@cmu.edu, Ignacio E.Grossmann We propose a Nested Benders Decomposition algorithm for mixed-integer problems arising in the planning of electric power systems. Our decomposition, which extends previous nested Benders methods by handling integer and continuous state variable, targets large-scale multi-period problems and allows us to investigate the impact of the number of representative days per year in the planning strategy over a long time horizon. The proposed algorithm is applied to a case study in the ERCOT region for a 30 year planning horizon, and demonstrate massive computational savings from our decomposition. Additionally, we compare the results for the different numbers of representative days. SA78B

30