Ambros Gleixner

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

    A massively parallel interior-point solver for linear energy system models with block structure

  • Ambros Gleixner
  • Thorsten Koch
  • Hannes Hobbie
  • Domink Möst
  • Daniel Rehfeldt
  • David Schönheit
    • Categories Linear Programming

    Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers—already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an … Read more

    First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method

  • Ambros Gleixner
  • Thorsten Koch
  • Nils-Christian Kempke
  • Daniel Rehfeldt
  • Svenja Uslu
    • Categories Linear Programming

    In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving … 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

    On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm

  • Ambros Gleixner
  • Felipe Serrano
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm applied to a particular … Read more

    Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms

  • Ambros Gleixner
  • Felipe Serrano
  • Benjamin Müller
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , , ,

    One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over … Read more

    Conflict-Driven Heuristics for Mixed Integer Programming

  • Ambros Gleixner
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming

    Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the … 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

    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

    Solving Quadratic Programs to High Precision using Scaled Iterative Refinement

  • Ambros Gleixner
  • Sebastian Sager
  • Tobias Weber
    • Categories Quadratic Programming Tags , , ,

    Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement … Read more