Integer Programming

A Note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs”

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming

    In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more

    The SCIP Optimization Suite 6.0

  • Michael Bastubbe
  • Leon Eifler
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Matthias Walter
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Franziska Schlösser
  • Christoph Schubert
  • Yuji Shinano
  • Merlin Viernickel
  • Fabian Wegscheider
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more

    Maximizing the storage capacity of gas networks: a global MINLP approach

  • Robert Burlacu
  • Martin Gross
  • Marc E. Pfetsch
  • Lars Schewe
  • Mathias Sirvent
  • Herbert Egger
  • Alexander Martin
  • Martin Skutella
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs Tags , , , ,

    In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler … Read more

    On the impact of running intersection inequalities for globally solving polynomial optimization problems

  • Alberto Del Pia
  • Aida Khajavirad
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory

    We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of a set of binary points satisfying a number of multilinear equations. Running intersection inequalities are a family of facet-defining inequalities for the … Read more

    Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Onur Tavaslioglu
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Stochastic Programming

    We introduce a generalized value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. We describe its fundamental properties, which we exploit through three algorithms to calculate it. We then show how this generalized value function can be used to reformulate two classes of mixed-integer optimization problems: two-stage stochastic … Read more

    The Supporting Hyperplane Optimization Toolkit

  • Jan Kronqvist
  • Andreas Lundell
  • Tapio Westerlund
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , , ,

    In this paper, an open source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The outer approximation is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended … Read more

    New facets for the consecutive ones polytope

  • Laura Brentegani
  • Luigi De Giovanni
  • Mattia Festa
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra Tags , ,

    A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear … Read more

    Data-Driven Chance Constrained Programs over Wasserstein Balls

  • Zhi Chen
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , ,

    We provide an exact deterministic reformulation for data-driven chance constrained programs over Wasserstein balls. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, our reformulation amounts to a mixed-integer conic program. In the special case of a Wasserstein ball with the $1$-norm or the $\infty$-norm, the cone is the nonnegative … Read more

    A Lagrange decomposition based Branch and Bound algorithm for the Optimal Mapping of Cloud Virtual Machines

  • Walid Ben-Ameur
  • Adam Ouorou
  • Guanglei Wang
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , ,

    One of the challenges of cloud computing is to optimally and efficiently assign virtual machines to physical machines. The aim of telecommunication operators is to mini- mize the mapping cost while respecting constraints regarding location, assignment and capacity. In this paper we first propose an exact formulation leading to a 0-1 bilinear constrained problem. Then … Read more

    The Integrated Last-Mile Transportation Problem

  • David Bergman
  • John Hooker
  • Arvind U. Raghunathan
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Scheduling

    Last-mile transportation (LMT) refers to any service that moves passengers from a hub of mass transportation (MT), such as air, boat, bus, or train, to destinations, such as a home or an office. In this paper, we introduce the problem of scheduling passengers jointly on MT and LMT services, with passengers sharing a car, van, … Read more