(Mixed) Integer Linear Programming

Two-row and two-column mixed-integer presolve using hash-based pairing methods

  • Weikun Chen
  • Ambros Gleixner
  • Dieter Weninger
  • Patrick Gemander
  • Leona Gottwald
  • Alexander Martin
    • Categories (Mixed) Integer Linear Programming, Optimization Software Benchmark, Polyhedra Tags , , ,

    In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more

    Mixed Integer Programming models for planning maintenance at offshore wind farms under uncertainty

  • Albert H. Schrotenboer
  • Evrim Ursavas
  • Iris F. A. Vis
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , , ,

    We introduce the Stochastic Maintenance Fleet Transportation Problem for Offshore wind farms (SMFTPO), in which a maintenance provider determines an optimal, medium-term planning for maintaining multiple wind farms while controlling for uncertainty in the maintenance tasks and weather conditions. Since the maintenance provider is typically not the owner of a wind farm, it needs to … Read more

    Multi-Row Intersection Cuts based on the Infinity Norm

  • Ricardo Fukasawa
  • Laurent Poirrier
  • Alinson S. Xavier
    • Categories (Mixed) Integer Linear Programming Tags , ,

    When generating multi-row intersection cuts for Mixed-Integer Linear Optimization problems, an important practical question is deciding which intersection cuts to use. Even when restricted to cuts that are facet-defining for the corner relaxation, the number of potential candidates is still very large, specially for instances of large size. In this paper, we introduce a subset … Read more

    MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library

  • Tobias Achterberg
  • Michael Bastubbe
  • Timo Berthold
  • Philipp M. Christophel
  • Gerald Gamrath
  • Ambros Gleixner
  • Gregor Hendel
  • Thorsten Koch
  • Jeff Linderoth
  • Marco E. Lübbecke
  • Hans D Mittelmann
  • Ted K. Ralphs
  • Kati Jarck
  • Derya Ozyurt
  • Domenico Salvagnin
  • Yuji Shinano
    • Categories (Mixed) Integer Linear Programming, Optimization Software Benchmark

    We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of 5,721 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using … Read more

    ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs

  • Henrik Andersson
  • Bjarne Grimstad
    • Categories (Mixed) Integer Linear Programming

    We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by many authors to probe for various model properties subject to input bounds. The formulation is obtained by programming each ReLU operator with a binary … Read more

    A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Algorithms and Software

  • Robert Apap
  • Ignacio E. Grossmann
  • Can Li
  • Juan Torres
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags

    This paper presents a tutorial on the state-of-the-art methodologies for the solution of two-stage (mixed-integer) linear stochastic programs and provides a list of software designed for this purpose. The methodologies are classifi ed according to the decomposition alternatives and the types of the variables in the problem. We review the fundamentals of Benders Decomposition, Dual Decomposition … Read more

    Relating Single-Scenario Facets to the Convex Hull of the Extensive Form of a Stochastic Single-Node Flow Polytope

  • Victor A. Gonzalez
  • Andrew J. Schaefer
  • Mehdi Hemmati
  • David T. Mildebrath
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Stochastic Programming Tags , ,

    Stochastic mixed-integer programs (SMIPs) are a widely-used modeling paradigm for sequential decision making under uncertainty. One popular solution approach to solving SMIPs is to solve the so-called “extensive form” directly as a large-scale (deterministic) mixed-integer program. In this work, we consider the question of when a facet-defining inequality for the convex hull of a deterministic, … Read more

    Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

  • Elena Fernandez
  • Markus Leitner
  • Ivana Ljubić
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Production and Logistics Tags , , , , , ,

    Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These … Read more

    Feeder Routing for Air-to-Air Refueling Operations

  • Christoph Hansknecht
  • Imke Joormann
  • Bernd Korn
  • Fabian Morscheck
  • Sebastian Stiller
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    We consider the problem of routing a fleet of feeders for civil air-to-air refueling operations. In the air-to-air refueling problem, a fixed set of cruisers requires refueling by a fleet of feeders at fixed locations and fixed points in time. A typical objective function is to minimize the fuel consumption or the total number of … Read more

    Globalized Robust Optimization with Gamma-Uncertainties

  • Andreas Bärmann
  • Christina Büsing
  • Frauke Liers
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Robust Optimization Tags , , ,

    Globalized robust optimization has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection depending on the distance of the realized scenario from the predefined uncertainty set. In this work, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its … Read more