Integer Programming

Improved Penalty Algorithm for Mixed Integer PDE Constrained Optimization (MIPDECO) Problems

  • Dominik Garmatter
  • Margherita Porcelli
  • Francesco Rinaldi
  • Martin Stoll
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Optimization of Systems modeled by PDEs Tags , , ,

    Optimal control problems including partial differential equation (PDE) as well as integer constraints merge the combinatorial difficulties of integer programming and the challenges related to large-scale systems resulting from discretized PDEs. So far, the Branch-and-Bound framework has been the most common solution strategy for such problems. In order to provide an alternative solution approach, especially … 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

    Integer Programming Formulations for Minimum Spanning Tree Interdiction

  • Foad Mahdavi Pajou
  • Jose L. Walteros
  • Ningji Wei
    • Categories Branch and Cut Algorithms, Integer Programming, Network Optimization Tags , , ,

    We consider a two-player interdiction problem staged over a graph where the leader’s objective is to minimize the cost of removing edges from the graph so that the follower’s objective, i.e., the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level $r$. Standard approaches for graph interdiction … 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 Stochastic Bin Packing Approach for Server Consolidation with Conflicts

  • Waltenegus Dargie
  • John Martinovic
  • Markus Hähnel
  • Guntram Scheithauer
    • Categories 0-1 Programming, Applications - Science and Engineering, Stochastic Programming Tags , ,

    The energy consumption of large-scale data centers or server clusters is expected to grow significantly in the next couple of years contributing to up to 13 percent of the worlwide energy demand in 2030. As the involved processing units require a disproportional amount of energy when they are idle, underutilized or overloaded, balancing the supply … Read more

    New facets and facet-generating procedures for the orientation model for vertex coloring problems

  • Diego Delle Donne
  • Javier Marenco
    • Categories Cutting Plane Approaches, Polyhedra Tags , ,

    In this work, we study the \emph{orientation model} for vertex coloring problems with the aim of finding partial descriptions of the associated polytopes. We present new families of valid inequalities, most of them supported by paths of the input graph. We develop facet-generating procedures for the associated polytopes, which we denominate \emph{path-lifting procedures}. Given a … 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