(Mixed) Integer Linear Programming

Interval-based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem

  • Natashia Boland
  • Mike Hewitt
  • Luke Marshall
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Transportation Tags

    We introduce an effective and efficient iterative algorithm for solving the Continuous-Time Service Network Design Problem. The algorithm achieves its efficiency by carefully and dynamically refining partially time-expanded network models so that only a small number of small integer programs, defined over these networks, need to be solved. An extensive computational study shows that the … Read more

    New Valid Inequalities for the Fixed-Charge and Single-Node Flow Polytopes

  • Adam N. Letchford
  • Georgia Souli
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    The most effective software packages for solving mixed 0-1 linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very … Read more

    Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems

  • Brian Dandurand
  • Kibaek Kim
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Stochastic Programming

    We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions … Read more

    Dynamic Courier Routing for a Food Delivery Service

  • Mark Karwan
  • Chase Murray
  • Zachary Steever
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation

    Services like Grubhub and UberEats have revolutionized the way that diners can find and order from restaurants. The standard business model for such services, however, allows diners to order from only one restaurant at a time. Inspired by a food delivery service in the southeastern United States, this paper proposes the framework for a more … Read more

    Empirical Bounds on Linear Regions of Deep Rectifier Networks

  • Srikumar Ramalingam
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Statistics

    One form of characterizing the expressiveness of a piecewise linear neural network is by the number of linear regions, or pieces, of the function modeled. We have observed substantial progress in this topic through lower and upper bounds on the maximum number of linear regions and a counting procedure. However, these bounds only account for … Read more

    Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations

  • Jacek Gondzio
  • E. Alper Yildirim
    • Categories (Mixed) Integer Linear Programming, Quadratic Programming Tags , , ,

    A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative mixed integer linear programming formulations. Our first formulation is based on casting a standard quadratic program … Read more

    Analysis of Models for the Stochastic Outpatient Procedure Scheduling Problem

  • Amy Cohn
  • Marina A. Epelman
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , , ,

    In this paper, we present a new stochastic mixed-integer linear programming model for the Stochastic Outpatient Procedure Scheduling Problem (SOPSP). In this problem, we schedule a day’s worth of procedures for a single provider, where each procedure has a known type and associated probability distribution of random duration. Our objective is to minimize the expectation … Read more

    Rapid prototyping of parallel primal heuristics for domain specific MIPs: Application to maritime inventory routing

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Transportation

    Parallel Alternating Criteria Search (PACS) relies on the combination of computer parallelism and Large Neighborhood Searches to attempt to deliver high quality solutions to any generic Mixed-Integer Program (MIP) quickly. While general-purpose primal heuristics are widely used due to their universal application, they are usually outperformed by domain-specific heuristics when optimizing a particular problem class. … Read more

    Chvátal’s Conjecture Holds for Ground Sets of Seven Elements

  • Leon Eifler
  • Ambros Gleixner
  • Jonad Pulaj
    • Categories (Mixed) Integer Linear Programming Tags

    We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer … Read more

    On robust fractional 0-1 programming

  • Colin Gillen
  • Andrés Gómez
  • Oleg A. Prokopyev
  • Erfan Mehmanchi
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Robust Optimization Tags , ,

    We study single- and multiple-ratio robust fractional 0-1 programming problems (RFPs). In particular, this work considers RFPs under a wide-range of disjoint and joint uncertainty sets, where the former implies separate uncertainty sets for each numerator and denominator, and the latter accounts for different forms of inter-relatedness between them. First, we demonstrate that, unlike the … Read more