Daniel Rehfeldt The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems-by using mathematical … Read more
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
The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the last 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. … Read more
Connectivity is a central concept in combinatorial optimization, graph theory, and operations research. In many applications, one is interested in finding an optimal subset of vertices with the essential requirement that the vertices are connected, but not how they are connected. I.e., it is not relevant, which edges are selected to obtain connectivity. Two natural … Read more
This article introduces new reduction techniques for the Steiner tree problem in graphs (SPG) and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. In particular, we introduce a generalization of the Steiner bottleneck distance—the arguably most important reduction concept for SPG. While … Read more
The prize-collecting Steiner tree problem (PCSTP) is a well-known generalization of the classic Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the 11th DIMACS Challenge in 2014, and since then, several PCSTP solvers have been introduced in the literature. Although these new solvers further, and often … Read more
Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers—already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an … Read more
In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving … Read more
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
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 … Read more