Informs Annual Meeting 2017

SB75

INFORMS Houston – 2017

2 - Consistency vs. Flexibility in Multi Objective Vehicle Routing Problems

achieves a $O(\frac{1}{t^{1.4-\epsilon}})$ convergence rate for all $\epsilon\in(0,1.4)$. We also show the convergence rate can be improved to $O(\frac{1}{t^2})$ if the objective function belongs to a special class. When the objective function is $\mu$-strongly convex and $L$-smooth, we show that it achieves a linear convergence rate of $O([ 1 - O( (\frac{\mu}{L})^{5/7} )]^t)$. 4 - Variable Partitioning for Distributed Optimization Richard Zheng, PhD Student, Georgia Institute of Technology, 6228 Mount Vernon Oaks Dr, Atlanta, GA, United States, richardzyc@gatech.edu Solving a large-scale optimization problem sequentially can be computational challenging. We focus on one of the most popular distributed approaches, dual decomposition and distributed sub-gradient methods. We explain that a partition of variables can critically affect the speed of convergence and highlight the importance of the number of dualized constraints. Then, we introduce a novel approach to find a partition that reduces the number of dualized constraints by utilizing a community detection algorithm from physics literature. Empirical experiments on a real application show that the proposed method significantly accelerates the convergence of the distributed sub-gradient method. 372E Advances in Integer Programming Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Akshay Gupte, Clemson University, Clemson University, Clemson, SC, 29634-0975, United States, agupte@clemson.edu 1 - Optimal Group Cuts Amitabh Basu, Johns Hopkins University, Department of Applied Mathematics and Statist, 100 Whitehead Hall, Baltimore, MD, 21218, United States, basu.amitabh@jhu.edu, Michele Conforti, Marco Di Summa We investigate natural measures of the quality of cutting planes such as depth of cut, volume cut off, and the so-called “merit index” introduced by Gomory and Johnson. We find the optimal cutting planes according to these measures for the infinite and finite group relaxations introduced by Gomory-Johnson. Interestingly, when the volume cut off is used as the measure, the optimal cuts turn out to be automorphisms of the well-known Gomory mixed-integer cut. The proofs uncover interesting connections with rearrangement inequalities in functional analysis and generalizations of the Brunn-Minkowski theorem to topological groups. 2 - Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding Juan Pablo Vielma, Massachusetts Institute of Technology, 77 Massachusetts Avenue, E62-561, Cambridge, MA, 02139, United States, jvielma@mit.edu There is often a significant trade-off between formulation strength and size in mixed integer programming. When modelling convex disjunctive constraints (e.g. unions of convex sets) this trade-off can be resolved by adding auxiliary continuous variables. However, adding these variables can result in a deterioration of the computational effectiveness of the formulation. We introduce a technique to construct formulations without these detrimental continuous auxiliary variables. We then show it can recover and generalize all known strong formulations without continuous auxiliary variables. 3 - Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools Joseph A.Huchette, MIT, 77 Massachusetts Avenue, Cambridge, MA, 02139, United States, huchette@mit.edu Piecewise linear functions are a central modeling primitive throughout optimization. In this work, we present novel mixed-integer programming (MIP) formulations for (nonconvex) piecewise linear functions. Leveraging recent advances in the systematic construction of MIP formulations for disjunctive sets, we derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations derived are small (logarithmic in the number of piecewise segments of the function domain) and strong, and we present extensive computational experiments in which they offer substantial computational performance gains over existing approaches. 4 - Approximating Integer Programs using the Lexicographic Order Akshay Gupte, Clemson University, Clemson University, Clemson, SC, United States, agupte@clemson.edu, Michael Eldredge The convex hull of integer points in a box that are bounded lexicographically above or below a threshold have a useful polyhedral structure. We attempt to solve integer optimization problems over a polytope by enforcing a split in the lexicographical order of the integer points in the polytope. We compare the cuts generated by this disjunction with cuts generated by elementary disjunctions. Here, we present our results. SB76

Mohsen Emadikhiav, University of Connecticut, Storrs, CT, United States, Mohsen.Emadikhiav@business.uconn.edu, David Bergman, David Bergman, Robert Day In this talk, we discuss a branch-and-price algorithm for a multi-objective consistent VRP with simultaneous pickups and deliveries, and analyze the tradeoffs between several classical VRP objectives. Our experimental results indicate that for short-term planning, enforcing consistency only marginally affects other objectives, but for real-time planning, particularly when there is high variability in order release times, enforcing consistency can significantly impact other objectives. 3 - A Branch-and-price Algorithm for a Vehicle Routing-allocation Problem Mohammad Reihaneh, University of Massachusetts, 277 Riverglade Dr, Apt 2, Amherst, MA, 01002, United States, mo.reihaneh@gmail.com, Ahmed Ghoniem We investigate a vehicle routing-allocation problem (VRAP) where the decision- maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective dynamic programming-based branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Our computational study demonstrates the efficacy of the proposed approach using a test-bed of 60 challenging problem instances. 4 - Vehicle Routing with Drones Amro El-Adle, Isenberg School of Management, UMass-Amherst, Amherst, MA, United States, aeladle@umass.edu, Ahmed Ghoniem, Mohamed Haouari We investigate a vehicle routing problem with drones in which customers may be served either by the vehicle or by a portable drone that is launched from the vehicle. A key consideration in this setting is to synchronize vehicle and drone operations. Models and optimization approaches are presented, along with a computational study. 372D Distributed and Large-Scale Optimization Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Ermin Wei, Northwestern University, Evanston, IL, 60208, United States, ermin.wei@northwestern.edu 1 - Asynchronous Distributed Newton Method Ermin Wei, Northwestern University, 2145 Sheridan Rd, Tech L310, Evanston, IL, 60208, United States, ermin.wei@northwestern.edu The problem of minimizing a sum of local convex objective functions over a networked system captures many important applications and has received much attention in the distributed optimization field. Most of existing work focuses on development of distributed algorithms under the presence of a central clock. The only known algorithms with convergence guarantees in asynchronous setup could achieve linear rate. In this work, we built upon existing literature to develop and analyze an asynchronous Newton method. We show that this algorithm converges almost surely and has superlinear rate in expectation. Numerical studies confirm superior performance against other existing asynchronous methods. 2 - Object-parallel Augmented Lagrangian Solution of Continuous Stochastic Programs Gyorgy Matyasfalvi, Rutgers University, 100 Rockafeller Road, Piscataway, NJ, 08854, United States, matyasfalvi@gmail.com, Jonathan Eckstein We describe an “object-parallel’ C++ approach to implementing iterative optimization methods, with the goal of coding the algorithms in a readable, MATLAB-like style, but with efficient parallel implementation of underlying low- level linear algebra operations. Recent advances in augmented Lagrangian algorithms and mathematical modeling environments, combined with our “object-parallel’ software development techniques suggest efficiently scalable solver implementations for stochastic programming problems, without employing decomposition methods. 3 - Accelerated Distributed Nesterov Gradient Descent Guannan Qu, Harvard University, Cambridge, MA, 02138, United States, guannan.q@gmail.com, Na Li This paper considers the distributed optimization problem over a network, where the objective is to optimize a global function formed by a sum of local functions. We develop an Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD) method. When the objective function is convex and smooth, we show that it SB75

62