Leon Eifler – Optimization Online

Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver

Published: 2024/03/22

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 ensure that all results remain provably correct, while sacrificing as little computational performance as possible in comparison to a pure floating-point implementation. The study also addresses the adaptation of certification … Read more

The SCIP Optimization Suite 9.0

Published: 2024/02/26

Jasper van Doornmalen

Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems branch-and-cut algorithm, Branch-and-price algorithm, column generation, constraint integer programming, linear programming, Mixed-integer Linear Programming (MILP), Mixed-integer nonlinear programming (MINLP), mixed-integer semidefinite programming, optimization solver, parallelization

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more

Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

Published: 2023/11/14

Leon Eifler

Ambros Gleixner

(Mixed) Integer Linear Programming, Linear Programming, Other Topics extended precision arithmetic, iterative refinement, linear programming, Mixed Integer Programs

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 errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: … Read more

A proof system for certifying symmetry and optimality reasoning in integer programming

Published: 2023/11/07, Updated: 2023/11/08

Jasper van Doornmalen

Leon Eifler

Ambros Gleixner

Christopher Hojny

(Mixed) Integer Linear Programming Certificate of correctness, cutting planes, mixed-integer programming, Proof system, symmetry handling

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 the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more

Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework

Published: 2023/03/22, Updated: 2023/07/26

Leon Eifler

Ambros Gleixner

(Mixed) Integer Linear Programming certificates, cutting planes, Mixed Integer Programs, rational arithmetic

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 computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably … Read more

The SCIP Optimization Suite 8.0

Published: 2021/12/16, Updated: 2022/01/31

Jasper van Doornmalen

Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization

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 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

A Computational Status Update for Exact Rational Mixed Integer Programming

Published: 2021/01/22

Leon Eifler

Ambros Gleixner

(Mixed) Integer Linear Programming certificate, correctness, exact computation, mixed-integer programming, rational arithmetic, symbolic computations

The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, … Read more

The SCIP Optimization Suite 7.0

Published: 2020/03/30

Matthias Miltenberger

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming benders decomposition, branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization, presolving, steiner tree optimization, tree size estimation

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 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

Chvátal’s Conjecture Holds for Ground Sets of Seven Elements

Published: 2018/09/05

Leon Eifler

Ambros Gleixner

Jonad Pulaj

(Mixed) Integer Linear Programming maximal intersecting families

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

Published: 2018/07/02, Updated: 2018/07/03

Matthias Miltenberger

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