Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

WD09

4 - Progress in the Branch-price-and-cut Solver GCG Marco Luebbecke, RWTH Aachen University, Operations Research, Kackertstr. 7, Aachen, D-52072, Germany, Michael Bastubbe, Christian Puchert, Jonas Witt GCG is a solver for mixed-integer linear programs. It implements a Dantzig-Wolfe (or similar) reformulation and a full-featured branch-price-and-cut algorithm. Information on how the reformulation should be performed can be given by the user in various ways. However, GCG can and usually does detect a model structure suited for reformulation all by itself. We report on recent developments that lead to the upcoming release 3.0. This includes a completely re-designed structure detection, new cutting planes, and experimental features like deciding whether a reformulation should be applied at all and a Benders decomposition extension. We show experiments and some use cases in which we applied GCG. n WD06 North Bldg 122C Global Optimization II Sponsored: Optimization/Global Optimization Sponsored Session Chair: Akang Wang, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States 1 - Global Optimization Algorithm to Solve the Equilibrium- constrained Program for Estimating Random-coefficient Demand Function Yu-Ching Lee, National Tsing Hua University, No 101, Section 2, Kuang-Fu Road, Engineering Building I, Hsinchu, Taiwan, Cy (Chor-yiu) Sin Recently, estimation problem of random-coefficient demand function using aggregate market level observations has been formulated as an equilibrium- constrained optimization program. This modeling technique successfully bridges the advance of nonlinear programming (NLP) solvers with important class of problem in demand estimation. NLP solvers are convenient and efficient in terms of implementation and computation for estimating demand. Nevertheless, a guarantee of global optimality is missing. In the talk we will discuss the importance of global optimality for this class of problem. Then, a global optimization algorithm will be presented to solve for a global optimal estimator. 2 - Bilevel Optimization Problem for Preferred Boarding Groups Viacheslav V. Kalashnikov, Tecnologico de Monterrey, (ITESM), Campus Monterrey, Ave Eugenio Garza Sada 2501 Sur, Monterrey, Nuevo Leon, 64849, Mexico We consider a bilevel optimization problem, in which the upper-level decisions are made by the airline’s management governing the proportion of preferred boarding passes (PBP) to be available, as well as the price of the latter. The economy class passengers find Nash equilibrium at the lower level by trying to minimize their flight cost, where the individual cost function has two components: the PBP price and the expected waiting time in the line to the check-in counters. As the optimality at the lower level provides the percentage of PBPs sold to have the minimum deviation from its value in the future sales, the Markov chain stable state technique is used to solve the problem. The model has a practical value. 3 - A Customized Branch and Bound Approach for Circle Packing Akang Wang, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, Chrysanthos Gounaris We present a custom-built linear relaxation and an associated branch-and-bound approach for solving circle packing problems to global optimality. We utilize a novel branching scheme based on circle-circle non-overlapping constraints, and we also employ concave envelopes to tighten the feasible domain. Extensive computational studies are performed on benchmark instances and the preliminary results demonstrate our approach’s superiority over the state-of-the- art general-purpose global solvers. 4 - New Underestimator and Branching Scheme for the Global Optimization of General Nonconvex Problems Ishan Bajaj, Texas A&M University, 3122 TAMU, College Station, TX, 77843, United States, Faruque Hasan The selection of the underestimator and branching scheme are central to the effectiveness of a branch-and-bound (B&B) algorithm. We propose to exploit a new class of edge-concave underestimators, constructed by subtracting a positive quadratic expression that overpowers all non-edge-concavities in the original function. We also propose a novel branching technique based on a univariate projection of the original multi-dimensional space into a single auxiliary space such that a function exists on this map whose global minima is the same as that of the original function. We will show the efficacy of the proposed relaxation and branching schemes with other methods in the literature.

n WD08 North Bldg 124A

Topics in Non-convex Optimization Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Mert Gurbuzbalaban, Rutgers University, Piscataway, NJ, 08854, United States Co-Chair: Nuri Denizcan Vanli, Massachusetts Institute of Technology, Cambridge, MA, 02141, United States 1 - Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability Belinda Tzen, University of Illinois at Urbana-Champaign, Urbana, IL, United States We study the path-wise behavior of the discrete-time Langevin algorithm for non-convex ERM via metastability. For a given local optimum of the empirical risk, we show that w.h.p., the path either ends up outside an e-neighborhood of this optimum by a short recurrence time; or it enters by then and stays until an exponentially-long escape time. This aligns with existing literature. Firstly, recurrence time is dimension independent, like convergence of deterministic gradient descent. Secondly, escape time is consistent with the Eyring-Kramers law; i.e., the Langevin scheme visits all local minima, with exponentially-long transit time. We use this to examine local generalization and optimality. 2 - Convergence Rate of Block-coordinate Maximization Burer-Monteiro Method for Solving Large SDPs Nuri Denizcan Vanli, Massachusetts Institute of Technology, 22 Palermo Street, Cambridge, MA, 02141, United States Semidefinite programming (SDP) with equality constraints arise in many optimization and learning problems, such as max-cut, community detection and robust PCA. Although SDPs can be solved to arbitrary precision in polynomial time, generic solvers do not scale well with the dimension of the problem. To address this issue, Burer and Monteiro proposed to reduce the dimension of the problem by imposing a low rank factorization and solve the resulting nonconvex problem. To solve this nonconvex problem, we propose a first-order method based on block coordinate ascent with exact line search. We provide convergence rate guarantees and computational results on large-scale problems. 3 - Momentum-Based Acceleration for Non-convex Stochastic Optimization Mert Gurbuzbalaban, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Building 32 / Room D632, Cambridge, MA, 02139, United States We consider stochastic non-convex optimization problems that arise in several applications including machine learning and the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm to solve them. We obtain the first finite-time global convergence guarantees for SGHMC in the context of both empirical and population risk minimization. Our results show SGHMC can achieve acceleration on a class of non-convex problems compared to overdamped Langevin MCMC approaches such as the stochastic gradient Langevin dynamics. This is joint work with Xuefeng Gao and Lingjiong Zhu. n WD09 North Bldg 124B Fairness and Transparency in Applied Operations Sponsored: Manufacturing & Service Oper Mgmt Sponsored Session Chair: Swati Gupta, PhD, Georgia Institute of Technology, Atlanta, GA, United States Co-Chair: John Silberholz 1 - Market Failure in Kidney Exchange Itai Ashlagi, Stanford University, Huang Engineering Center, 475 Via Ortega, Stanford, CA, 94305, United States We find that kidney exchange markets suffer from traditional market failure that reduce transplants by over 25%. We document that the market is highly fragmented and inefficient. We propose a model to illustrate two sources of inefficiency: hospitals do not internalize their patients’ benefits and current mechanisms provide sub-optimal rewards to hospitals. Eliminating this inefficiency requires a combined approach that uses mechanisms and solves agency problems.

497