67 citations · 151 across the 41 of their papers we have counts for
40 papers · 1 filter
A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem
Mohammed Ghannam, Ambros Gleixner, Gioni Mexi +1
The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is ass…
CHAP: A Hybrid GPU-CPU Heuristic for MIP
Gennesaret Kharistio Tjusila, Alexander Hoen, Nils-Christian Kempke +5
We present CHAP (Coordinating Heuristics Across Platforms) a GPU-CPU-hybrid primal heuristic framework for mixed-integer programming. CHAP adopts a portfolio approach where it coor…
Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs
Nils-Christian Kempke, Stephen J Maher, Daniel Rehfeldt +3
We present a structure-aware parallel presolve framework for arrowhead linear programs (AHLPs) in high-performance computing (HPC) environments, integrated into the parallel interi…
Clique Probing for Mixed-Integer Programs
Jacob von Holly-Ponientzietz, Alexander Hoen, Mark Turner +1
Probing is an important presolving technique in mixed-integer programming solvers. It selects binary variables, tentatively fixes them to 0 and 1, and performs propagation to deduc…
The SCIP Optimization Suite 10.0
Christopher Hojny, Mathieu Besançon, Ksenia Bestuzheva +31
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This…
Branch and price for nonlinear production-maintenance scheduling in complex machinery
João Dionísio, Ambros Gleixner, João Pedro Pedroso +1
This paper proposes a mixed-integer nonlinear programming approach for joint scheduling of long-term maintenance decisions and short-term production for groups of complex machines…
Analyzing the numerical correctness of branch-and-bound decisions for mixed-integer programming
Alexander Hoen, Ambros Gleixner
Most state-of-the-art branch-and-bound solvers for mixed-integer linear programming rely on limited-precision floating-point arithmetic and use numerical tolerances when reasoning…
Cut-based Conflict Analysis in Mixed Integer Programming
Gioni Mexi, Felipe Serrano, Timo Berthold +2
For almost two decades, mixed integer programming (MIP) solvers have used graph-based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this…
MIP-DD: A Delta Debugger for Mixed Integer Programming Solvers
Alexander Hoen, Dominik Kamp, Ambros Gleixner
The recent performance improvements in mixed-integer programming (MIP) have been accompanied by a significantly increased complexity of the codes of MIP solvers, which poses challe…
Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver
Sander Borst, Leon Eifler, Ambros Gleixner
This paper presents the integration of constraint propagation and dual proof analysis in an exact, roundoff-error-free MIP solver. The authors employ safe rounding methods to ensur…
A diving heuristic for mixed-integer problems with unbounded semi-continuous variables
Katrin Halbig, Alexander Hoen, Ambros Gleixner +2
Semi-continuous decision variables arise naturally in many real-world applications. They are defined to take either value zero or any value within a specified range, and occur main…
Branch and Price for the Length-Constrained Cycle Partition Problem
Mohammed Ghannam, Gioni Mexi, Edward Lam +1
The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is ass…
The SCIP Optimization Suite 9.0
Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva +28
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This…
Branch and Cut for Partitioning a Graph into a Cycle of Clusters
Leon Eifler, Jakob Witzig, Ambros Gleixner
In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights tha…
Certifying MIP-based Presolve Reductions for 0-1 Integer Linear Programs
Alexander Hoen, Andy Oertel, Ambros Gleixner +1
It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations m…
The MIP Workshop 2023 Computational Competition on Reoptimization
Suresh Bolusani, Mathieu Besançon, Ambros Gleixner +5
This paper describes the computational challenge developed for a computational competition held in 2023 for the anniversary of the Mixed Integer Programming Work…
Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization
Leon Eifler, Jules Nicolas-Thouvenin, Ambros Gleixner
This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff erro…
A proof system for certifying symmetry and optimality reasoning in integer programming
Jasper van Doornmalen, Leon Eifler, Ambros Gleixner +1
We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes t…
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
Gioni Mexi, Timo Berthold, Ambros Gleixner +1
Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with gene…
Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization
Gioni Mexi, Mathieu Besançon, Suresh Bolusani +3
We introduce Scylla, a primal heuristic for mixed-integer optimization problems. It exploits approximate solves of the Linear Programming relaxations through the matrix-free Primal…
Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
Ksenia Bestuzheva, Helena Völker, Ambros Gleixner
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the glob…
Online Learning for Scheduling MIP Heuristics
Antonia Chmiela, Ambros Gleixner, Pawel Lichocki +1
Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Sin…
Enabling Research through the SCIP Optimization Suite 8.0
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen +32
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of…
Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework
Leon Eifler, Ambros Gleixner
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one comput…