Informs Annual Meeting 2017

MD76

INFORMS Houston – 2017

2 - Globally Convergent Algorithms for Two Layer Neural Network Problems Digvijay Boob, Georgia Institute of Technology, digvijaybb40@gatech.edu, Guanghui Lan

4 - A Unified Decomposition Matheuristic for Assembly, Production and Inventory Routing Jean-Francois Cordeau, HEC Montreal, 3000 Cote-Sainte-Catherine, Montreal, QC, H3T.2A7, Canada, jean-francois.cordeau@hec.ca, Masoud Chitsaz, Raf Jans We introduce a decomposition-based heuristic for the assembly-routing problem and two related problems: the production-routing problem (PRP) and the inventory-routing problem (IRP). The heuristic relies on the iterative solution of different subproblems. The first phase determines a setup schedule while the second phase optimizes production quantities, supplier visit schedules and shipment quantities. The third phase solves a vehicle routing problem for each period in the planning horizon. Using the same parameter setting for all problems and instances, we obtained 818 new best known solutions out of 2,628 standard IRP and PRP test instances. 5 - Vehicle Routing Problems with Synchronized Visits and Stochastic Travel or Service Times: Applications in Healthcare Louis-Martin Rousseau, Polythechnique Montreal, Cp 6079 Succ Centre-Ville, Montreal, QC, H3C 3A7, Canada, louis-martin.rousseau@polymtl.ca, Seyed Hossein Hashemi Doulabi, Gilles Pesant We study the vehicle routing problems with synchronized visits (VRPS) where travel and service times are stochastic or time-dependent. We formulate VRPS as a two-stage stochastic programming model with integer variables in both stages. An advantage of the proposed model is that it does not have any big-M constraints. We consider applications in home-health care scheduling problem, as well as operating room scheduling with stochastic durations. We prove that the integrality constraints on second-stage variables are trivial, and therefore we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem. 372F Joint session OPT/Practice: Applications of Conic Optimization for Energy Systems Sponsored: Optimization, Linear and Conic Optimization Sponsored Session Chair: Ramtin Madani, The University of Texas at Arlington, Arlington, TX, 76015, United States, ramtin.madani@uta.edu 1 - Polynomial Optimization, Interpolation, and its Application to Power Systems Cédric Josz, ERC Postdoctoral Fellow, Laboratory for Analysis and Architecture of Systems LAAS.CNRS, 7 Avenue du Colonel Roche, Toulouse, 31400, France, cedric.josz@gmail.com Polynomial optimization in complex numbers is used to model oscillatory phenomena in various applications such as electric power systems, imaging science, signal processing, and quantum mechanics. We propose a hierarchy of complex semidefinite programs as well as a semidefinite programming solver in complex numbers to find global solutions with reduced computational burden. We apply these to large-scale sections of the European HV electricity grid. We also propose an algorithm for extracting global solutions once optimality has been reached, and show that it provides a variant to Prony’s method, which is used for instance to determine inter-area oscillations from phasor measurement units. 2 - Power System State Estimation Problem: Optimal Sensor Placement Salar Fattahi, PhD Candidate, University of California-Berkeley, Berkeley, CA, United States, fattahi@berkeley.edu, Javad Lavaei This talk is concerned with the power system state estimation (PSSE) problem. Given a set of noisy measurements, PSSE aims at estimating the complex voltages at all buses of the network. Recently, we have shown that a conic optimization problem could effectively estimate the state of the system. In this talk, we use the notion of weighted algebraic connectivity to devise a sparsity-promoting technique that would determine where to place the sensors so that the estimation error associated with the conic formulation of PSSE is minimized. 3 - A Massively Scalable Approach to Power System Scheduling Ramtin Madani, Assistant Professor, The University of Texas at Arlington, 3004 Franciscan Dr, Apt 1835, Arlington, TX, 76015, United States, ramtin.madani@uta.edu, Alper Atamturk, Ali Davoudi A computational method is introduced, which is capable of approaching power system scheduling problems with a considerably large number of binary variables, while handling nonlinear equations that govern the flow of electricity. We design a family of linear and conic inequalities to form a polynomial-time solvable surrogate, with the aim of finding a near globally optimal point for the original problem. The proposed method is demonstrated on large-scale problems based on real-world European grid data, for which feasible decisions are obtained within provably small gaps from global optimality. MD77

Neural network can be trained with stochastic gradient descent to achieve good performance in many applications. Central problem in their training involves optimizing a nonconvex loss function whose theoretical analysis is hard. In this work, we give an algorithm to converge to global optimal solution with high probability under some assumptions about activation functions, distribution of the data and width of neural network. 3 - A Convex Gradient-based Approach for Profit Optimization in Online Advertising Demand-side Platforms Paul Grigas, UC Berkeley, 4177 Etcheverry Hall, University of California, Berkeley, CA, 94720-1777, United States, pgrigas@berkeley.edu, Alfonso Lobos, Zheng Wen, Kuang-chih Lee We develop an optimization model for the management of a demand-side platform (DSP), whereby the DSP aims to maximize its own profit while acquiring valuable impressions for its advertiser clients in a real-time bidding environment. We use convex relaxation to develop a tractable convex dual problem, which, due to the properties of second-price auctions, may be solved efficiently with non- smooth stochastic gradient methods. We propose a two-phase solution procedure and demonstrate evidence of strong performance guarantees. 4 - Approximation Algorithms for Bilevel Programming Saeed Ghadimi, Princeton University, Princeton, NJ, United States, sghadimi@princeton.edu, Mengdi Wang In this talk, we consider the classical setting for bilevel programming where the objective function of the outer problem depends on the optimal solution of inner one. We present gradient type algorithms for solving this class of problems and obtain an optimal iteration complexity for the outer problem and (nearly) optimal one for the inner problem. We also discuss convergence of stochastic approximation algorithms for solving this class of problems under stochastic setting. 372E Integrated Methods and Decomposition Approaches Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Joris Kinable, Carnegie Mellon University, Pittsburgh, PA, 15213, United States, jkinable@cs.cmu.edu 1 - Discrete Nonlinear Optimization by State-Space Decomposition David Bergman, McKinsey & Company, 4106 Stearns HIll Road, In recent years the use of decision diagrams for discrete optimization has grown in popularity, with a focus on linear integer optimization. In this talk, an expansion to nonlinear objective functions will be discussed. The work proposes the use of decision diagrams to model the objective function, which are then linked together through a network flow linearization. Experimental results on problems arising in revenue management, portfolio optimization, and healthcare exhibit orders-of-magnitude improvement in solution times compared with state- of-the-art nonlinear solvers. 2 - Dynamic Programming Bounds from Decision Diagrams John Hooker, Carnegie Mellon University, Tepper School of Business, Pittsburgh, PA, 15213, United States, jh38@andrew.cmu.edu We investigate the potential of relaxed decision diagrams to provide bounds on the optimal value of dynamic programming formulations. We prove general conditions under which a node merger operation in the diagram yields a valid relaxation. We then focus on job sequencing problems with state-dependent processing times, because no useful bounding mechanism currently exists for these problems. Computational experiments show that, surprisingly, relaxed diagrams prove the optimal value when their size is only a small fraction of the size of an exact diagram. 3 - Integer and Constraint Programming for Batch Annealing Process Planning Willem-Jan Van Hoeve, Carnegie Mellon University, Tepper School of Business, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, vanhoeve@andrew.cmu.edu, Sridhar R.Tayur We describe an optimization application in the context of steel manufacturing, to design and schedule batches for annealing furnaces. Our solution approach uses a two-phase decomposition. The first phase groups together orders into batches using a mixed-integer linear programming model. The second phase assigns the batches to furnaces and schedules them over time, using constraint programming. Our solution has been developed for operational use in two plants of a steel manufacturer in North America. Waltham, MA, 02451, United States, david.bergman@business.uconn.edu MD76

264