Informs Annual Meeting 2017

MC78

INFORMS Houston – 2017

MC76

During the last two decades, primal-dual algorithms enjoyed significant advances in solving convex optimization problems in conic form over symmetric cones. However, many other highly demanded optimization problems lack such advances. To make the gap closer, we develop a theory of infeasible-start primal- dual algorithms for problems in the “Domain-Driven” setup, which covers many interesting problems including those with a “natural” conic formulation. After presenting our techniques, and our convergence theorems, we introduce our developing Matlab-based code, DDS, that solves a large class of problems including LP, SOCP, SDP, QCQP, geometric programming, and entropy programming. 3 - Polynomial Optimization with Sum-of-Squares Interpolants Sercan Yildiz, University of North Carolina at Chapel Hill, SAMSI, 19 TW. Alexander Drive, Research Triangle Park, NC, 27703, United States, syildiz@email.unc.edu, David Papp Sums-of-squares relaxations define a hierarchy of lower bounds for polynomial optimization problems. Although these relaxations can be represented as semidefinite programs, solving these semidefinite programs poses practical challenges at higher levels of the hierarchy. First, their size depends quadratically on the size of the sums-of-squares relaxation. Second, numerical problems are often encountered in their solution. In this talk, we show that non-symmetric conic programming and polynomial interpolation techniques can be used to optimize efficiently over the sums-of-squares cone. 381A Electric Energy Storage Planning: Methods and Results Sponsored: Energy, Natural Res & the Environment Electricity Sponsored Session Chair: Elaine Hale, National Renewable Energy Laboratory, elaine.hale@nrel.gov 1 - Investing in Grid-scale Energy Storage: Placement in Transmission vs. Distribution Systems? MC78 If current trends continue, electrochemical energy storage will soon be widely deployed to perform various grid services in both transmission and distribution systems. It is expected that a significant portion of these devices will be owned by merchant, i.e. profit-seeking, entities. Since compensation and regulatory requirements in the distribution and transmission systems vary, merchant investors need to carefully optimize investments in energy storage to achieve maximum gains. This presentation will describe a modeling framework that makes it possible for merchant investors to trade-off investments in energy storage between the transmission and distribution systems. 2 - Optimized Dispatch for Concentrating Solar Power Subject to Forecast Uncertainty Michael J. Wagner, National Renewable Energy Laboratory, 15013 Denver West Pkwy, MS-RSF033, Golden, CO, 80401, United States, Michael.Wagner@nrel.gov Concentrating Solar Power (CSP) systems are capable of efficient storage of thermal energy that can then be dispatched to generate electricity at night or during cloudy periods. The optimal energy dispatch schedule depends on weather and pricing forecasts which are inherently uncertain. Furthermore, these forecasts and their uncertainty may be correlated depending on local market structure and prominence of renewable generators on the grid. We present methods and results for optimal dispatch of CSP systems subject to weather and pricing forecast uncertainty. The model is implemented in the publicly available System Advisor Model software, and design sizing sensitivity results are discussed. 3 - Planning for Concentrating Solar Power in the Western United States Elaine Thompson Hale, National Renewable Energy Laboratory, 15013 Denver West Parkway, MS RSF300, Golden, CO, 80401, United States, elaine.hale@nrel.gov, Brady Stoll, Jennie Jorgenson Concentrating solar power with thermal energy storage (CSP-TES) is a flexible renewable energy technology that could be an attractive complement to solar photovoltaics (PV) and wind in the Southwestern United States (U.S.). When and where such investments may be attractive depends on future policies, fuel prices, and cost trajectories of alternative technologies such as PV and battery storage. We apply the Resource Planning Model (RPM), which is a capacity expansion model designed for regional power systems and high levels of renewable generation and complementary flexible technologies, to this question for a region centered on current U.S. CSP deployment and looking out to 2035. Yury Dvorkin, New York University, 185 Stevens Way NE, Paul Allen Center, Room AE104R, New York, NY, 11201, United States, dvorkin@nyu.edu

372E Dynamic Programming Based Methods for Discrete Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Selvaprabu Nadarajah, College of Business, University of Illinois at Chicago, Chicago, IL, 60607, United States, selvan@uic.edu Co-Chair: Andre Augusto Cire, University of Toronto-Scarborough, Toronto, ON, M1C-1A4, Canada, acire@utsc.utoronto.ca 1 - An Exact Algorithm for a Dynamic Knapsack Problem Alejandro Toriello, Georgia Institute of Technology, Atlanta, GA, United States, atoriello@isye.gatech.edu, Daniel Blado We examine a stochastic knapsack problem with random item sizes that are realized upon an attempted insertion. The goal is to maximize expected profit and the process ends after a failed insertion. We propose an exact algorithm based on a reformulation of the value function linear program that dynamically prices variables to refine a value function approximation and generates cutting planes to maintain a dual bound. We discuss the algorithm’s theoretical properties and its empirical performance. 2 - Approximate Linear Programming for Discrete Optimization Selvaprabu Nadarajah, College of Business, University of Illinois at Chicago, 601 South Morgan Street,, U. H.2406, Chicago, IL, 60607, United States, selvan@uic.edu, Andre Augusto Cire We consider a hierarchy of approximate linear programming based approximations to a general class of discrete optimization problems. We present theory regarding the relative quality of these approximations and test them on challenging discrete optimization problems arising in practice. 3 - Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Action and Scalar State Giacomo Nannicini, IBM T.J. Watson, 1101 Kitchawan Road, Yorktown Heights, NY, United States, nannicini@us.ibm.com, Nir Halman We propose an FPTAS for stochastic dynamic programs with multidimensional action, scalar state, convex piecewise linear costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing how to deal with multidimensional action spaces and with vectors of continuous random variables under suitable conditions, therefore getting one step closer to overcoming the curses of dimensionality of dynamic programming. 372F Algorithms for Semidefinite Programming and Conic Optimization Sponsored: Optimization, Linear and Conic Optimization Sponsored Session Chair: Sercan Yildiz, University of North Carolina at Chapel Hill, Statistical and Applied Mathematical Sciences Institute, 19 TW Alexander Drive, Research Triangle Park, NC, 27703, United States, syildiz@email.unc.edu Co-Chair: David Papp, North Carolina State University, Raleigh, NC, 27606, United States, dpapp@ncsu.edu 1 - Solving Conic Systems via Projection and Rescaling Negar Soheili Azad, University of Illinois-Chicago, 601 S. Morgan Street, University Hall 2416, Chicago, IL, 60607, United States, nazad@uic.edu, Javier F.Pena We propose a projection and rescaling algorithm to solve conic feasibility problems. Our algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov’s projection-based method for linear feasibility problems. As in these predecessors, each main iteration of our algorithm contains two steps: a basic procedure and a rescaling step. We compare the performance of different basic procedures and study the rescaling algorithm’s performance on linear feasibility problems. 2 - Convex Optimization via Domain Driven Barriers and Primal Dual Algorithms Mehdi Karimi, University of Waterloo, 200 University Ave W, Waterloo, ON, N2L.3G1, Canada, m7karimi@uwaterloo.ca, Levent Tuncel MC77

231