2016 INFORMS Annual Meeting Program

399 / 561

INFORMS Nashville – 2016
399
2 - Solving The Split Delivery Vehicle Routing Problem With
A Priori Split
Xingyin Wang, University of Maryland, College Park, MD, 20742,
United States, , 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,
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.
WB12
104B-MCC
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,
1 - 2-level Polytopes: Recent Results And Open Problems
Yuri Faenza, Columbia University, New York, NY, United States,
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,
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, , 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, 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
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,
1 - A New Deterministic Parallel Framework For Mixed
Integer Programs
Michael Perregaard, FICO,
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,
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,
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,
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
Chair: David Sungjun Choi, Carnegie Mellon University,
5000 Forbes Avenue, Pittsburgh, PA, 15213, United States,
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, ,
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.
WB15