Gleixner, Ambros
Refine
Year of publication
Document Type
- ZIB-Report (47)
- Article (37)
- In Proceedings (29)
- Master's Thesis (2)
- Doctoral Thesis (1)
Is part of the Bibliography
- no (116)
Keywords
- linear programming (5)
- MINLP (4)
- parallelization (4)
- Linear programming (3)
- branch-and-cut (3)
- energy system models (3)
- mixed-integer nonlinear programming (3)
- mixed-integer semidefinite programming (3)
- nonconvex (3)
- propagation (3)
- Branch-and-cut (2)
- Branch-and-price (2)
- Column generation (2)
- Constraint integer programming (2)
- MIP (2)
- MIQCP (2)
- Markov State Models (2)
- Mixed-Integer Programming (2)
- Mixed-integer linear programming (2)
- Mixed-integer nonlinear programming (2)
- Mixed-integer semidefinite programming (2)
- NESS (2)
- Non-reversible Markov Processes (2)
- OBBT (2)
- Optimization solver (2)
- Parallelization (2)
- Steiner tree optimization (2)
- block structure (2)
- branch-and-price (2)
- column generation framework (2)
- constraint integer programming (2)
- extremal combinatorics (2)
- global optimization (2)
- high performance computing (2)
- interior-point method (2)
- mixed-integer linear programming (2)
- mixed-integer quadratically constrained programming (2)
- optimality-based bound tightening (2)
- optimization solver (2)
- optimization-based bound tightening (2)
- preprocessing (2)
- presolving (2)
- Exact linear programming (1)
- IP (1)
- Iterative refinement (1)
- LP solver (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- Large Neighborhood Search (1)
- MINLP solver (1)
- MINLP, global optimization, operative planning, water supply networks (1)
- MIP solver (1)
- MIPLIB (1)
- Mengenüberdeckung (1)
- Mixed Integer Programming (1)
- Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Nonlinear Programming (1)
- Nachbarschaftssuche (1)
- Nonconvex Optimization (1)
- Primal Heuristic (1)
- Primalheuristik (1)
- Problem Instances (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- Steiner tree solver (1)
- algorithm selection (1)
- bilinear terms (1)
- bound tightening (1)
- branch-cut-and-price framework (1)
- computational (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- exact rational integer programming (1)
- exact rational mixed integer programming (1)
- generic column generation (1)
- high-performance computing (1)
- interior-point methods (1)
- large neighborhood search (1)
- mixed integer programming (1)
- mixed integer programming; primal heuristics; conflict analysis; branch-and-bound (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer quadratically constrained programs (1)
- modeling (1)
- multi-criteria optimization (1)
- nonconvex optimization (1)
- parallel branch-and-bound (1)
- perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study (1)
- primal heuristic (1)
- projection (1)
- separation (1)
- set covering (1)
- simplex method (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- surrogate relaxation (1)
Institute
This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition’s format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.
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 that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming 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 new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.
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 must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on – integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further.
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 correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641–649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances to exact optimality and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set.
The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights
(2022)
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, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.