MODAL-SynLab
Refine
Year of publication
Document Type
- ZIB-Report (102)
- Article (90)
- In Proceedings (70)
- Master's Thesis (10)
- Proceedings (5)
- Book chapter (4)
- Doctoral Thesis (4)
- Bachelor's Thesis (3)
- Software (2)
- In Collection (1)
Keywords
- mixed integer programming (11)
- mixed-integer programming (8)
- linear programming (6)
- parallelization (5)
- MINLP (4)
- branch-and-bound (4)
- presolving (4)
- Column generation (3)
- Mixed-Integer Programming (3)
- Mixed-integer linear programming (3)
- branch-and-cut (3)
- branching rule (3)
- constraint integer programming (3)
- domain propagation (3)
- energy system models (3)
- large neighborhood search (3)
- maximum-weight connected subgraph (3)
- mixed-integer semidefinite programming (3)
- preprocessing (3)
- primal heuristics (3)
- Branch-and-cut (2)
- Branch-and-price (2)
- Constraint integer programming (2)
- Linear programming (2)
- Markov State Models (2)
- Mixed Integer Programming (2)
- Mixed-Integer Nonlinear Programming (2)
- Mixed-integer nonlinear programming (2)
- Mixed-integer semidefinite programming (2)
- NESS (2)
- Non-reversible Markov Processes (2)
- Optimization solver (2)
- Parallelization (2)
- SCIP (2)
- Steiner Tree Problem (2)
- Steiner tree optimization (2)
- Steiner tree problems (2)
- block structure (2)
- branch-and-bound parallelization (2)
- branch-and-price (2)
- column generation framework (2)
- extremal combinatorics (2)
- global optimization (2)
- high performance computing (2)
- integer optimization (2)
- integer programming (2)
- interior-point method (2)
- maximum-weight connected subgraph problem (2)
- mixed integer nonlinear programming (2)
- mixed-integer linear programming (2)
- mixed-integer nonlinear programming (2)
- optimization solver (2)
- parallelization framework (2)
- primal heuristic (2)
- prize-collecting Steiner tree problem (2)
- propagation (2)
- Algorithm Analysis (1)
- Artificial Intelligence (1)
- Branch and bound method (1)
- Branch-and-Bound, Mixed-Integer Programming (1)
- Branch-and-Cut (1)
- Clinch number (1)
- Combinatorial optimization (1)
- Convex envelopes (1)
- Cutting planes (1)
- DIMACS Challenge (1)
- Elimination number (1)
- Energy supply systems (1)
- Expansion planning of energy networks (1)
- Gurobi (1)
- Hierarchical approach (1)
- Infeasibility Detection (1)
- Integer programming (1)
- Intersection cuts (1)
- Iterative algorithm (1)
- LP solver (1)
- Linear Programming (1)
- MINLP solver (1)
- MIP (1)
- MIP solver (1)
- MIPLIB (1)
- Machine Learning (1)
- Mathematical Programming (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness (1)
- Mixed-Integer Programming solvers (1)
- Network Design (1)
- Newton barrier method (1)
- Node merging (1)
- OBBT (1)
- Optimal design (1)
- Optimal operation (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Parallel processing (1)
- Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack (1)
- Progress measures (1)
- QCQPs (1)
- Quadratic Optimization (1)
- Quadratic-free sets (1)
- Racing ParaSCIP (1)
- Restart (1)
- Round-robin tournament (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- SCIP-Jack (1)
- Sports league (1)
- Steiner Tree Problem Variants (1)
- Steiner tree (1)
- Steiner tree problem (1)
- Steiner tree solver (1)
- Steiner tree variants (1)
- Tail assignment (1)
- Tiebreaking criteria (1)
- Ubiquity Generator Framework (1)
- adaptive search behavior (1)
- algorithm selection (1)
- analytic center (1)
- anlalytic center (1)
- bilinear terms (1)
- bivariate functions (1)
- bound tightening (1)
- branch and bound (1)
- branch-cut-and-price framework (1)
- conflict analysis (1)
- convex envelope (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- cut selection (1)
- deterministic parallelism (1)
- dual degeneracy (1)
- dual proof analysis (1)
- exact rational integer programming (1)
- exact rational mixed integer programming (1)
- extremal combinatorics, extremal set theory, cutting plane, exact integer programming (1)
- fix-and-propagate (1)
- forecasting (1)
- generic column generation (1)
- graph transformation (1)
- high-performance computing (1)
- interior point algorithm (1)
- interior-point methods (1)
- linear underestimator (1)
- machine learning (1)
- mixed integer programming; primal heuristics; conflict analysis; branch-and-bound (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- mixed-integer quadratically constrained programs (1)
- modeling (1)
- multi armed bandit (1)
- multi armed bandit problem (1)
- multi-criteria optimization (1)
- no-good learning (1)
- nonconvex (1)
- nonconvex optimization (1)
- optimality prediction (1)
- optimality-based bound tightening (1)
- optimization (1)
- optimization software (1)
- optimization-based bound tightening (1)
- parallel (1)
- parallel branch-and-bound (1)
- parallel computing (1)
- perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study (1)
- portfolio solvers (1)
- prize-collecting Steiner tree (1)
- projection (1)
- reduction techniques (1)
- reliability branching (1)
- rounding (1)
- search strategy (1)
- separation (1)
- simplex (1)
- simplex method (1)
- software information, software citation, mathematical research data (1)
- solution learning (1)
- solver software (1)
- strong branching (1)
- supercomputing (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- surrogate relaxation (1)
- tree-size estimates (1)
Institute
- Mathematical Optimization (204)
- Mathematical Optimization Methods (159)
- AI in Society, Science, and Technology (66)
- Applied Algorithmic Intelligence Methods (33)
- Mathematical Algorithmic Intelligence (17)
- Digital Data and Information for Society, Science, and Culture (7)
- Mathematics of Transportation and Logistics (4)
- Computational Molecular Design (2)
- Mathematics of Telecommunication (2)
- Numerical Mathematics (2)
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.
We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances.
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.
Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better.
It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.
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.