Source-linked AI summary
The SCIP Optimization Suite 9.0
Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, Liding Xu
TL;DR
The report addresses how to extend and improve a constraint-integer-programming optimization suite across solving methods, interfaces, and companion components. It presents SCIP 9.0’s new and improved algorithms and interfaces, reporting overall improvements in performance and reliability while noting that some new cut-selection schemes are not generally superior and remain lower-priority options.
Problem
The report examines how the SCIP Optimization Suite can improve optimization solving capabilities, interfaces, and supporting software across diverse mathematical programming settings.
Method
The report presents and evaluates new algorithms, solver components, interfaces, and enhancements across SCIP and the other packages in the SCIP Optimization Suite.
Results
The SCIP Optimization Suite 9.0 provides new functionality with improved performance and reliability, including enhanced symmetry handling, nonlinear processing, heuristics, separation, branching, and interfaces.
Takeaways & Limitations
SCIP 9.0 broadens the suite’s optimization capabilities through algorithmic improvements and expanded language and solver-component interfaces.
Takeaways & Limitations
The new dynamic and ensemble cut-selection schemes showed no general improvement or were unreliable for some MINLPs, so they remain lower-priority options.
Abstract
from arXiv · showhide
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 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.
1 Introduction
The SCIP Optimization Suite 9.0 report presents improvements to SCIP’s solving process and extensions across the suite’s optimization software, interfaces, and supporting frameworks. The release adds new capabilities in symmetry handling, nonlinear processing, heuristics, separation, branching, interfaces, and related suite components.
- Suite structure: The SCIP Optimization Suite combines SCIP with complementary packages for modeling, presolving, LP solving, parallelization, decomposition, and semidefinite optimization.SCIP is designed for constraint integer programs and uses branch-cut-and-price with LP relaxations, extensible constraint handlers, and plugin-based solving components.
- Core SCIP improvements: SCIP 9.0 improves symmetry handling for non-binary variables, custom constraints, and signed permutation symmetries.The release also adds symmetry preprocessing interfaces to nauty and sassy.
- Core SCIP improvements: SCIP 9.0 adds a signomial constraint handler and improves nonlinear processing, including a callback for linearizing expressions at specified solution points.The release also includes cut-strengthening for nonlinear constraints.
- Core SCIP improvements: New primal-solving features include indicator diving, extensions to dynamic partition search, and online scheduling of primal heuristics.The scheduler uses online learning to control large-neighborhood-search and diving heuristic types together.
- Core SCIP improvements: SCIP 9.0 introduces the Lagromory separator, improves cut selection, and adds GMI branching as a tie-breaker within existing branching rules.GMI branching is incorporated into the existing scoring function, while Lagromory is a new separator based on a relax-and-cut framework.
- Suite extensions: The suite expands its interfaces with russcip for Rust, SCIP++ for C++, and PySoPlex for Python, while also improving SoPlex, PaPILO, UG, GCG, and SCIP-SDP.The report also covers improvements to distributed computing, Dantzig-Wolfe decompositions, and semidefinite optimization support.
2 Overall Performance Improvements for MILP and MINLP
SCIP 9.0 was evaluated against SCIP 8.0 using fixed settings across MILP and MINLP test sets. The newer version solved more instances and generally reduced solving time and branch-and-bound tree size, especially on harder instances.
- Evaluation setup: The comparison used fixed algorithmic settings, SCIP 8.0.0 as baseline, and SCIP 9.0.0 with updated SoPlex and PaPILO versions.Runs used identical machines, single-threaded execution, and five random seeds per instance.
- Evaluation setup: The MILP test set comprised 158 instances, evaluated through 790 runs across five random seeds.Instances came from MIPLIB 2017 and were selected based on prior solvability or new solvability with SCIP 9.0.0.
- MILP performance: SCIP 9.0 solved 19 more MILP instances than SCIP 8.0, was 2% faster on affected instances, and reduced average tree size by 17% on both-solved instances.On instances requiring at least 1000 seconds in at least one setting, the speedup was 6%.
- MINLP performance: SCIP 9.0 solved 5 more MINLP instances and improved shifted-geometric-mean performance by about 4% in time and 13% in nodes overall.The MINLP test set contained 179 instances and was evaluated with five seeds, yielding 810 runs.
- MINLP performance: The performance gains increased with instance difficulty, reaching 20% on the hardest MINLP test set.The cited passage begins the corresponding node comparison but does not provide its completed value.
3 SCIP
SCIP 9.0 expands symmetry handling and nonlinear processing while adding mechanisms for custom constraints, signed permutations, and signomial cuts. These changes broaden the solver’s supported structures, although the signomial handler remains computationally expensive and disabled by default.
- Symmetry detection: Symmetry detection was restructured to support custom constraints and signed permutation symmetries, with added interfaces to nauty and sassy.Constraint handlers can provide permutation and signed-permutation symmetry graphs through optional callbacks.
- Symmetry handling: SCIP 9.0 generalizes symmetry handling to non-binary variables and permits previously incompatible symmetry-reduction classes to be applied simultaneously.This change improved MIPLIB 2017 performance by 5.90%, with a 25.40% running-time improvement on instances taking at least 1000 seconds.
- Symmetry detection: SCIP detects permutation symmetries by finding automorphisms of colored graphs that encode variables, constraints, coefficients, bounds, and dependencies.Local graphs are combined into a global symmetry detection graph through a constraint-handler callback.
- Nonlinear handling: SCIP 9.0 adds a signomial nonlinear handler that generates cutting planes for generally nonconvex signomial constraints.It also improves quadratic handling and adds a callback that can request expression linearization at a feasible solution to tighten the LP relaxation.
- Nonlinear handling: Signomial estimation can be costly because the relevant LP has size exponential in h, and the handler is disabled by default.An advanced parameter limits the maximum h it can manage, while users can enable the handler explicitly.
- Nonlinear handling: SCIP 9.0 strengthens quadratic intersection cuts by allowing them to incorporate integrality information through monoidal strengthening.The cited passage describes this as an extension of the quadratic handler introduced in SCIP 8.0.
3.3 Primal Heuristics
SCIP 9.0 adds and extends primal heuristics, cut separators, cut selection, and branching to improve solution search and exploit structural information. Several additions remain optional or have instance-dependent benefits.
- Indicator diving: The indicatordiving heuristic handles violated indicator constraints for semi-continuous variables with infinite upper bounds.It examines integral binary indicator variables and fixes them according to their LP values relative to the lower bound.
- Primal heuristics: DPS can now initialize its partition from the LP solution at the end of node processing.The calling point is controlled by heuristics/dps/timing.
- Primal heuristics: SCIP 9.0 introduces online learning that dynamically adapts the application of primal heuristics, jointly controlling Large Neighborhood Search and Diving.This extends earlier bandit-based adaptive heuristics.
- Cut generation: The Lagromory separator uses a relax-and-cut framework with enhancements designed for branch-and-cut trees.It improves harder instances requiring at least 1000 seconds but increases solving time on many easier instances, so it is off by default.
- Cut selection: The ensemble and dynamic cut selectors add richer scoring, filtering, stopping, and pairwise-efficacy criteria, but neither is the default because benefits are not generally established.Ensemble is unreliable on MINLPs with high-density cuts, while dynamic filtering has not shown a general improvement over cutsel/hybrid.
- Branching: SCIP 9.0 adds GMI-cut efficacy terms to branching scores and introduces a new branching criterion available standalone and within hybrid branching.Normalized GMI efficacy is recorded per separation round and contributes through configurable weights.
4 SoPlex
SoPlex 6.0 adds incremental precision boosting for exact rational LP solving, complementing iterative refinement. SCIP 9.0 also provides an LP interface for the open-source HiGHS solver.
- SoPlex 6.0: SoPlex 6.0 supports incremental precision boosting for exact rational LP solving alongside iterative refinement.Both methods are enabled by default and combined through an outer precision-boosting loop with inner iterative refinement.
5 PaPILO
PaPILO 2.2 adds proof logging for presolving binary programs, producing machine-verifiable certificates while introducing measurable runtime overhead. The feature is currently limited to pseudo-Boolean problems.
- Proof logging: PaPILO 2.2 adds proof logging to generate machine-verifiable certificates for solver computations.The feature supports certifying presolving transformations and objective updates through the VeriPB format.
- Scope: Proof logging is currently supported only for binary pseudo-Boolean problems.VeriPB supports this problem class, so the PaPILO feature does not yet cover general LP or MIP presolving.
- Performance: 27% to 54% is the reported runtime overhead of proof logging on the evaluated test sets.For 99% of decision instances, overhead per applied transaction is below 0.186 milliseconds.
- Performance: Proof logging remains practically viable in the reported experiments despite running sequentially while PaPILO presolvers run in parallel.The experiments used selected binary programs from MIPLIB 2017 and PB16.
6 Interfaces
SCIP 9.0 expands its language and solver interfaces, fixes portability and compatibility issues, and adds tools for modeling and plugin development. New interfaces include Rust and C++ bindings for SCIP and a Python wrapper for SoPlex.
- JSCIPOpt: JSCIPOpt fixes build, library-selection, binary-compatibility, integer-width, and portability problems.The fixes include validating SCIP_DIR, avoiding unsafe hardcoded layouts for dynamic linking, mapping SCIP Longint to 64-bit Java, and removing unnecessary POSIX mv usage.
- Python interfaces: PySCIPOpt is automatically included in standard PyPI installations for supported x86-64 systems, and PySCIPOpt-ML formulates machine-learning models into MIPs.Custom SCIP installations still require building PySCIPOpt from source.
- Existing interfaces: The Julia interface now exposes heuristic, branching, and cut-selection plugins through its high-level interface and callback mechanism.This extends existing access to constraint handler and separator plugins.
- New interfaces: SCIP 9.0 adds Rust and C++ interfaces for SCIP and a Python interface named PySoPlex for SoPlex.The Rust interface combines direct C-API access with a limited safe wrapper, while SCIP++ provides memory management and type-safe parameter methods.
- PySoPlex: PySoPlex provides Python access to SoPlex's C interface after installing SoPlex and configuring SOPLEX_DIR.Its installation was tested on Linux and Mac OS.
7 The UG Framework
UG parallelizes branch-and-bound base solvers across shared-memory and distributed environments, with version 1.0 broadening this into a high-level task-parallelization framework. The SCIP 9.0 release adds interface compatibility, bug fixes, and appropriate optimality-gap handling.
- 7 The UG Framework: UG was designed to parallelize powerful branch-and-bound base solvers in shared-memory and distributed computing environments.FiberSCIP uses shared memory, while ParaSCIP targets distributed computing.
- 7 The UG Framework: UG version 1.0 generalizes the framework beyond branch-and-bound tree search to parallelize other solver types and support more flexible task parallelization.
- 7 The UG Framework: The UG 1.0 beta released with SCIP 9.0 catches up with SCIP interface changes and includes additional bug fixes, but few new features.
- 7 The UG Framework: An optimality-gap limit can be set for the original instance through the SCIP parameter file supplied with the -sl option.The LoadCoordinator handles the gap limit before distributing the presolved instance.
8 The GCG Decomposition Solver
GCG automatically turns SCIP into a branch-and-price or branch-and-Benders-cut solver by detecting decomposable model structure and constructing the corresponding reformulation. Version 3.6 mainly improves the code base, API consistency, score customization, and Python extensibility.
- 8 The GCG Decomposition Solver: GCG automatically detects model structures suitable for Dantzig-Wolfe reformulation or Benders decomposition and performs the associated algorithmics without user interaction.Users provide the model, while GCG handles reformulation, Benders cuts, and column generation.
- 8 The GCG Decomposition Solver: GCG 3.6 replaces the DEC API prefix with GCG for consistent naming, with no major algorithmic changes.
- 8 The GCG Decomposition Solver: The score implementation was refactored to make adding user-defined decomposition scores easier.
- 8 The GCG Decomposition Solver: PyGCGOpt mirrors the GCG changes and lets users add their own classifiers and scores to customize decomposition detection.
9 SCIP-SDP
SCIP-SDP extends SCIP for mixed-integer semidefinite programs using SDP-based branch-and-bound by default, while also supporting an LP-based approach. Version 4.3.0 adds symmetry and conflict-analysis capabilities alongside presolving, cut-generation, and licensing changes.
- 9 SCIP-SDP: SCIP-SDP solves mixed-integer semidefinite programs with an SDP-based branch-and-bound approach by default and also supports an LP-based approach.Which approach is faster depends on the instance.
- 9.1 Symmetry Handling of MISDPs: Formulation symmetries can be detected with graph automorphism algorithms, while SCIP-SDP does not exploit symmetries in SDP matrix solutions.
- 9.1 Symmetry Handling of MISDPs: 34.00% speed-up was observed for the 21 MISDP instances containing symmetry, compared with about 4.00% across all instances.
- 9.1 Symmetry Handling of MISDPs: SCIP-SDP changed its symmetry-detection graph to use one node per nonzero matrix entry connected to dimension nodes.
- 9.2 Conflict Analysis for MISDPs: For each feasible or infeasible node, SCIP-SDP generates conflict constraint (9), stores it, and performs bound propagation.The resulting testset performance change was about 8% in both speed-up and node reduction.
- 9 SCIP-SDP: The SCIP-SDP license changed to Apache 2.0.
- 9.3 Other Improvements: SCIP-SDP also improves presolving and cut generation, supports CMIR inequalities by default in its LP-based approach, and extends dual-solution handling for conflict analysis.
10 Final Remarks
SCIP Optimization Suite 9.0 combines solver improvements, interface additions, and component extensions across SCIP, SoPlex, PaPILO, UG, GCG, and SCIP-SDP. Benchmark results report gains in solved instances, time, and branch-and-bound nodes for both MILP and MINLP.
- 10 Final Remarks: SCIP 9.0 adds improved symmetry handling, new cut selection schemes, GMI branching, a HiGHS LP interface, and AMPL reader improvements.
- 10 Final Remarks: New and improved interfaces include Rust and C++ interfaces for SCIP, PySoPlex, enhanced AMPL and Java interfaces, PySCIPOpt installation through PyPI, and PySCIPOpt-ML.
- 10 Final Remarks: SoPlex adds incremental precision boosting for exact rational LP solving, while PaPILO adds proof logging for machine-verifiable presolving certificates.
- 10 Final Remarks: SCIP-SDP adds symmetry handling and conflict analysis for MISDPs, alongside further presolving and cut-generation improvements.
- 10 Final Remarks: 19 more MILP instances were solved, with a 2% speedup on affected instances and a 17% reduction in nodes for instances solved by both versions.
Contributions of the Authors
The authors contributed implementation, extension, maintenance, and infrastructure work across SCIP and its surrounding optimization software ecosystem. Their contributions span symmetry, nonlinear handling, heuristics, cutting, branching, interfaces, solver components, testing, and reliability.
- Core SCIP functionality: Authors implemented symmetry detection and interfaces connecting SCIP with nauty, sassy, and bliss.
- Core SCIP functionality: The release adds a signomial nonlinear handler and monoidal strengthening for quadratic constraints.
- Core SCIP functionality: Authors extended or implemented indicator diving, DPS, online scheduling, Lagromory separation, ensemble cut selection, dynamic cut selection, and branching improvements.
- Interfaces and supporting components: A HiGHS LP interface, AMPL reader and interface extensions, OBBT propagation, and proof logging in PaPILO were also developed.
- Interfaces and supporting components: The team maintained and expanded JSCIPOpt, PySCIPOpt, SCIP.jl, russcip, SCIP++, and PySoPlex interfaces, including PySCIPOpt installation through PyPI.
- Ecosystem and reliability: Contributors improved GCG and SCIP-SDP, fixed bugs and file-reader issues, added reproducible debugging support, and worked on testing, distributions, and website development.
Author Affiliations
The listed contributors are affiliated with the University of Bayreuth and the Zuse Institute Berlin.
- Affiliations: Dominik Kamp is affiliated with the University of Bayreuth, Chair of Economathematics, in Bayreuth, Germany.
- Affiliations: The affiliations represent institutions in Bayreuth and Berlin, Germany.
- Affiliations: Mark Turner is affiliated with the Zuse Institute Berlin, Department A2IM, in Berlin, Germany.