Refine
Year of publication
Document Type
- ZIB-Report (10)
- In Proceedings (4)
- Article (2)
Is part of the Bibliography
- no (16)
Keywords
- linear programming (3)
- mixed-integer semidefinite programming (3)
- Steiner tree optimization (2)
- branch-and-cut (2)
- branch-and-price (2)
- column generation framework (2)
- constraint integer programming (2)
- mixed-integer linear programming (2)
- mixed-integer nonlinear programming (2)
- optimization solver (2)
- parallelization (2)
- Branch-and-Cut (1)
- DIMACS Challenge (1)
- LP solver (1)
- MINLP solver (1)
- MIP solver (1)
- MIPLIB (1)
- Mixed Integer Programming (1)
- Mixed-Integer Programming (1)
- Node merging (1)
- Parallel processing (1)
- Racing ParaSCIP (1)
- SCIP-Jack (1)
- Steiner Tree Problem (1)
- Steiner tree problem (1)
- Steiner tree solver (1)
- Steiner tree variants (1)
- Ubiquity Generator Framework (1)
- branch-and-bound (1)
- branch-cut-and-price framework (1)
- generic column generation (1)
- integer programming (1)
- maximum-weight connected subgraph (1)
- mixed-integer linear and nonlinear programming (1)
- modeling (1)
- multi-criteria optimization (1)
- parallel branch-and-bound (1)
- parallel computing (1)
- prize-collecting Steiner tree (1)
- simplex method (1)
- supercomputing (1)
Institute
- Mathematical Optimization Methods (16) (remove)
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.
SCIP-Jack: An exact high performance solver for Steiner tree problems in graphs and related problems
(2021)
The Steiner tree problem in graphs is one of the classic combinatorial
optimization problems. Furthermore, many related problems, such as the rectilinear Steiner tree problem or the maximum-weight connected subgraph problem, have been described in the literature—with a wide range of practical applications. To embrace this wealth of problem classes, the solver SCIP-JACK has been developed as an exact framework for classic Steiner tree and 11 related problems. Moreover,
the solver comes with both shared- and distributed memory extensions by means of the UG framework. Besides its versatility, SCIP-JACK is highly competitive for most of the 12 problem classes it can solve, as for instance demonstrated by its top ranking in the recent PACE 2018 Challenge. This article describes the current state of SCIP-JACK and provides up-to-date computational results, including several instances that can now be solved for the first time to optimality.
The SCIP Optimization Suite provides a collection of software packages for
mathematical optimization centered around the constraint integer programming frame-
work 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 mixed-integer linear op-
timization problems and can be used stand-alone or integrated into SCIP via a presolver
plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im-
provements in the Benders’ decomposition solver of SCIP, user-defined decomposition
structures can be read, which are used by the automated Benders’ decomposition solver
and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation
that is used to predict the completion of the overall solving process and potentially
trigger restarts. Moreover, substantial performance improvements of the MIP core were
achieved by new developments in presolving, primal heuristics, branching rules, conflict
analysis, and symmetry handling. Last, not least, the report presents updates to other
components and extensions of the SCIP Optimization Suite, in particular, the LP solver
SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best-known solutions to instances from the benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
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 for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added
to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.
In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.
This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.