2016 INFORMS Annual Meeting Program

WB15

INFORMS Nashville – 2016

2 - Solving The Split Delivery Vehicle Routing Problem With A Priori Split Xingyin Wang, University of Maryland, College Park, MD, 20742, United States, wang_xingyin@yahoo.com, Ping Chen, Bruce L Golden, Edward Andrew Wasil In the split delivery vehicle routing problem (SDVRP), a customer’s demand is allowed to be delivered by more than one vehicle. From a practitioner’s point of view, the state-of-the-art heuristics are often difficult to implement and usually take long computing times. We propose an efficient and easily implemented approach to solve the SDVRP using an a priori split strategy combined with a capacitated VRP solver. Our computational experiments show that our algorithm is overall much more efficient and produces results that are comparable to those from the state-of-the-art approaches. 3 - A Computation - Implementation Parallelization Approach For Computation - Time Limited Vehicle Routing Problem With Soft Time Windows Bahar Cavdar, Middle East Technical Univeristy, Universiteler Mahallesi, Dumlupinar Bulvari No: 1, Ankara, 06800, Turkey, bcavdar@metu.edu.tr, Joel Sokol Focusing on real-time and time-sensitive routing problems with soft time windows, we develop a new tabu search algorithm which uses a preprocessing step to eliminate unpromising moves and avoids exact computation of time window violations to speed up the computation. We also implement our algorithm using a Computation-Implementation Parallelization approach and show that almost all computation-time can be embedded into the implementation of the solution without hurting the solution quality. Polyhedral Methods in Combinatorial Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Carla Michini, University of Wisconsin, 330 North Orchard Street, Madison, WI, 53715, United States, michini@wisc.edu 1 - 2-level Polytopes: Recent Results And Open Problems Yuri Faenza, Columbia University, New York, NY, United States, yuri.faenza@gmail.com 2-level polytopes are a generalization of stable set polytopes of perfect graphs. They naturally appear in several areas of mathematics, including polyhedral combinatorics, combinatorial optimization, and statistics. Those polytopes have received quite some attention in the last years because of their connections with the theory of extended formulations and the prominent log rank conjecture in communication complexity. Still, many questions about their structure have not been answered yet. In this talk, I will survey known results and present open problems and promising research directions. 2 - Approximation Algorithm For Structured Packing IPs Qianyi Wang, Georgia Institute of Technology, qianyi.wang@gatech.edu, Santanu Subhas Dey, Marco Molinaro In this talk, we present an approximation algorithm for sparse structured packing IPs. In order to apply this algorithm, we first solve a series of sub-IPs derived from the original instance. Next, we construct a feasible solution according to the sparsity structure of the constraint matrix. The performance guarantee of this algorithm is a graph-theoretical parameter that depends on the sparsity structure only. 3 - Totally Unimodular Congestion Games Carla Michini, University of Wisconsin, Madison, WI, United States, michini@wisc.edu, Alberto Del Pia, Michael C Ferris We define Totally Unimodular (TU) Congestion Games, where the players’ strategies are binary vectors inside polyhedra with TU constraint matrices. In the symmetric case, we design strongly polynomial-time algorithms to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state, if the delay functions are weakly convex. We also show how to extend our technique to matroid congestion games. In the asymmetric case, we prove that for some combinatorial TU congestion games (i) it is PLS-complete to find a pure Nash equilibrium even in case of linear delay functions, and (ii) it is NP-hard to compute a socially optimal state, even in case of weakly convex delay functions. 4 - Learning To Dynamically Select Primal Heuristics In MIP Branch-and-bound Elias B Khalil, Georgia Institute of Technology, Atlanta, GA, 30332, United States, lyes@gatech.edu, Bistra Dilkina, George L Nemhauser, Shabbir Ahmed A variety of primal heuristics have been proposed in the MIP literature, with varying computational cost and effectiveness in finding good feasible solutions. At each node of a branch-and-bound search tree, the MIP solver must select some heuristics and run them, with the goal of finding a better feasible solution. We formalize this decision-making problem, and propose a theoretical framework for WB12 104B-MCC

analyzing algorithms that solve it. Towards creating better decision-making policies for primal heuristics, we show how Machine Learning can be leveraged to predict whether a primal heuristic will find an incumbent at a given node. Promising experimental results on MIPLIB with SCIP will be presented.

WB13 104C-MCC Advances in Integer Programming Software Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Imre Polik, Optimization Solver Developer, SAS, SAS, Cary, NC, 27513, United States, Imre.Polik@sas.com 1 - A New Deterministic Parallel Framework For Mixed Integer Programs Michael Perregaard, FICO, MichaelPerregaard@fico.com We present a new framework for solving MIPs in parallel on modern CPUs with large core counts. It has been designed from the ground up to be deterministic, scalable and asymmetric. We provide computational results demonstrating its performance and scalability within the latest FICO Xpress-Optimizer release. 2 - The SAS MILP Solver: Current Status And Future Developments Philipp M. Christophel, SAS Institute Inc., Mainz, Germany, philipp.christophel@sas.com We give an overview of the current status of the SAS mixed integer linear programming (MILP) solver that is part of the SAS/OR product. The focus will be on describing recent development efforts such as presolver techniques and cutting plane generators. 3 - Performance Improvements And New Features In The Gurobi Optimizer Zonghao Gu, Gurobi Optimization, gu@gurobi.com This talk will cover the latest developments in the Gurobi Optimizer, which include conflict analysis, new cutting planes and improved separation, new and improved heuristics. These developments enhance the performance of our new Gurobi 7.0 release. The release also includes several major new features and we will give an overview of these features. 4 - Recent Advances In Ibm Ilog Cplex Optimizer Andrea Tramontani, IBM Italy, Via Martin Luther King, 38/2, Bologna, 40132, Italy, andrea.tramontani@it.ibm.com This talk will cover the latest developments in the CPLEX Optimizer. We will present some of the new features and algorithmic techniques recently added to CPLEX, and we will give benchmark results to assess the performance improvements achieved in the latest CPLEX version. WB15 104E-MCC Detection of Structure and Anomalous Patterns in Data Sponsored: Artificial Intelligence Sponsored Session 1 - Efficient Discovery Of Heterogeneous Treatment Effects In Randomized Experiments Via Anomalous Pattern Detection Edward McFowland, Assistant Professor, University of Minnesota, Minneapolis, MN, United States, emcfowla@umn.edu, Satya Venkata Somanchi, Daniel B Neill There is a growing literature on the use of machine learning to estimate heterogeneous treatment effects across subpopulations in randomized experiments. However, each proposed method makes a set of restrictive assumptions about the intervention’s effects, the underlying data generating processes, and which subpopulation-level effects to explicitly estimate. Moreover, the majority of the literature provides no guidance on identifying the most significantly affected subpopulations. Therefore, we propose a new method for automatically identifying the subpopulation which experiences the largest distributional change as a result of the intervention, while making minimal assumptions. Chair: David Sungjun Choi, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, davidch@andrew.cmu.edu

399