1

Enabling Research through the SCIP Optimization Suite 8.0

2
3
4
5
6
7
8
9
10
11
12
13

KSENIA BESTUZHEVA, MATHIEU BESANÇON, WEI-KUN CHEN, ANTONIA CHMIELA, TIM
DONKIEWICZ, JASPER VAN DOORNMALEN, LEON EIFLER, OLIVER GAUL, GERALD GAMRATH, AMBROS GLEIXNER, LEONA GOTTWALD, CHRISTOPH GRACZYK, KATRIN HALBIG,
ALEXANDER HOEN, CHRISTOPHER HOJNY, ROLF VAN DER HULST, THORSTEN KOCH,
MARCO LÜBBECKE, STEPHEN J. MAHER, FREDERIC MATTER, ERIK MÜHMER, BENJAMIN
MÜLLER, MARC E. PFETSCH, DANIEL REHFELDT, STEFFAN SCHLEIN, FRANZISKA SCHLÖSSER,
FELIPE SERRANO, YUJI SHINANO, BORO SOFRANAC, MARK TURNER, STEFAN VIGERSKE,FABIAN WEGSCHEIDER, PHILIPP WELLNER, DIETER WENINGER, and JAKOB WITZIG

14
15
16
17
18

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 paper 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

19version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Further,20

the paper gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities

21

for user interaction with the framework, and the latest developments in several extensions built upon SCIP.

2223

CCS Concepts: • Theory of computation → Mixed discrete-continuous optimization; Parallel algorithms; Branch-and-bound;24• Mathematics of computing → Solvers; Mathematical software performance.

25
26

Additional Key Words and Phrases: Constraint integer programming, linear programming, mixed-integer linear programming,

27

mixed-integer nonlinear programming, optimization solver, branch-and-cut, branch-and-price, column generation, parallelization,

28

mixed-integer semidefinite programming

29
30
31

ACM Reference Format:
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver

32

Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf

33

van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch,

34

Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian

35
36
37
38
39
40
41
42
43
44

Authors’ address: Ksenia Bestuzheva, bestuzheva@zib.de; Mathieu Besançon, besancon@zib.de; Wei-Kun Chen, chenweikun@bit.edu.cn; Antonia Chmiela,
chmiela@zib.de; Tim Donkiewicz, tim.donkiewicz@rwth-aachen.de; Jasper van Doornmalen, m.j.v.doornmalen@tue.nl; Leon Eifler, eifler@zib.de; Oliver
Gaul, oliver.gaul@rwth-aachen.de; Gerald Gamrath, gamrath@zib.de; Ambros Gleixner, gleixner@zib.de; Leona Gottwald, gottwald@zib.de; Christoph
Graczyk, graczyk@zib.de; Katrin Halbig, katrin.halbig@fau.de; Alexander Hoen, hoen@zib.de; Christopher Hojny, c.hojny@tue.nl; Rolf van der Hulst,
r.p.vanderhulst@utwente.nl; Thorsten Koch, koch@zib.de; Marco Lübbecke, marco.luebbecke@rwth-aachen.de; Stephen J. Maher, s.j.maher@exeter.ac.uk;
Frederic Matter, matter@mathematik.tu-darmstadt.de; Erik Mühmer, erik.muehmer@rwth-aachen.de; Benjamin Müller, benjamin.mueller@zib.de; Marc
E. Pfetsch, pfetsch@mathematik.tu-darmstadt.de; Daniel Rehfeldt, rehfeldt@zib.de; Steffan Schlein, steffan.schlein@rwth-aachen.de; Franziska Schlösser,
schloesser@zib.de; Felipe Serrano, serrano@zib.de; Yuji Shinano, shinano@zib.de; Boro Sofranac, sofranac@zib.de; Mark Turner, turner@zib.de; Stefan
Vigerske, svigerske@gams.com; Fabian Wegscheider, wegscheider@zib.de; Philipp Wellner, p.we@fu-berlin.de; Dieter Weninger, dieter.weninger@fau.de;Jakob Witzig, witzig@zib.de.

45
46
47
48
49
50

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.
© 2022 Association for Computing Machinery.
Manuscript submitted to ACM

51
52

Manuscript submitted to ACM

1

2Bestuzheva et al.

53

Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig. 2022. Enabling Research through the SCIP Optimization Suite 8.0.

54

1, 1 (September 2022), 20 pages. https://doi.org/XXXXXXX.XXXXXXX

55
56
57

1

INTRODUCTION

58
59

The SCIP Optimization Suite comprises a set of complementary software packages designed to model and solve a large

60

variety of mathematical optimization problems: the modeling language Zimpl [34], the presolving library PaPILO, the61

linear programming solver SoPlex [73], the constraint integer programming solver SCIP [2], which can be used as

62
63
64

a fast standalone global solver for mixed-integer linear and nonlinear programs and a flexible branch-cut-and-priceframework, the automatic decomposition solver GCG [23], and the UG framework for solver parallelization [57].

65

All six tools can be downloaded in source code and are freely available for members of noncommercial and academic

66

institutions. Development and bugfix branches of SCIP, SoPlex and PaPILO are mirrored under https://github.com/

67
68

orgs/scipopt on a daily basis. They are accompanied by several extensions for solving specific problem classes such as

69

the award-winning Steiner tree solver SCIP-Jack [22] and the mixed-integer semidefinite programming (MISDP) solver

70

SCIP-SDP [20]. This paper discusses the capacity of SCIP as a software and research tool and presents the evolving

71

possibilities for working with the SCIP Optimization Suite 8.0, both as a black-box toolbox and as a framework with

72
73
74
75

possibilties of interaction and extension.
Background. SCIP is a branch-cut-and-price framework for solving different types of optimization problems, most76

importantly, mixed-integer linear programs (MILPs) and mixed-integer nonlinear programs (MINLPs). MINLPs are

77

optimization problems of the form78

min 𝑐 ⊤𝑥79

s.t. 𝐴𝑥 ≥ 𝑏,

80
81
82
83

𝑔 ≤ 𝑔𝑘 (𝑥) ≤ 𝑔𝑘𝑘for all 𝑘 ∈ M,

𝑥 𝑖 ≤ 𝑥𝑖 ≤ 𝑥 𝑖

for all 𝑖 ∈ N,

𝑥𝑖 ∈ Z

for all 𝑖 ∈ I,

(1)

84
85
86
87

(ℓ )
(ℓ )
(𝑛)
(𝑛)
defined by 𝑐 ∈ R𝑛 , 𝐴 ∈ R𝑚 ×𝑛 , 𝑏 ∈ R𝑚 , 𝑔, 𝑔 ∈ R𝑚 , 𝑔 : R𝑛 → R𝑚 , 𝑥, 𝑥 ∈ R𝑛 , the index set of integer variables

88

I ⊆ N B {1, . . . , 𝑛} and the index set of nonlinear constraints M B {1, . . . , 𝑚𝑛 }. We assume that 𝑔 is specified in89

algebraic form using basic expressions that are known to SCIP. The usage of R B R ∪ {−∞, ∞} allows for variables

90
91
92

that are free or bounded only in one direction (we assume that no variable is fixed to ±∞). In the absence of nonlinear
constraints 𝑔 ≤ 𝑔(𝑥) ≤ 𝑔, the problem becomes an MILP.

93

SCIP is not restricted to solving MI(N)LPs, but is a framework for solving constraint integer programs (CIPs), a

94

generalization of the former two problem classes. The introduction of CIPs was motivated by the modeling flexibility95
96

of constraint programming and the algorithmic requirements of integrating it with efficient solution techniques

97

available for MILPs. Later on, this framework allowed for the integration of MINLPs. Roughly speaking, CIPs are

98

finite-dimensional optimization problems with arbitrary constraints and a linear objective function that satisfy the99

following property: if all integer variables are fixed, the remaining subproblem must form a linear or nonlinear program.

100
101

The core of SCIP coordinates a central branch-cut-and-price algorithm that is augmented by a collection of plugins.

102

The methods for processing constraints of a given type are implemented in constraint handler plugins. The default

103

plugins included in the SCIP Optimization Suite provide tools to solve MI(N)LPs as well as some problems from

104

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0

3105

constraint programming, satisfiability testing and pseudo-Boolean optimization. In this way, advanced methods like106

primal heuristics, branching rules, and cutting plane separators can be integrated using a pre-defined interface. SCIP

107
108
109

comes with many such plugins that enhance MI(N)LP performance, and new plugins can be created by users. This
design and solving process is described in more detail by Achterberg [1].

110The core solving engine also includes PaPILO, which provides an additional presolving procedure that is called by

111

SCIP, and the linear programming (LP) solver SoPlex which is used by default for solving the LP relaxations within the

112
113

branch-cut-and-price algorithm. Interfaces to several external LP solvers exist, and new ones can be added by users.

114

The flexibility of this framework and its design, which is centered around the capacity for extension and customization,115

are aimed at making SCIP a versatile tool to be used by optimization researchers and practitioners. The possibility

116

to modify the solving process by including own solver components enables users to test their techniques within a

117
118

general-purpose branch-cut-and-price framework.

119

The extensions of SCIP that are included in the SCIP Optimization Suite showcase the use of SCIP as a basis for the120

users’ own projects. GCG extends SCIP to automatically detect problem structure and generically apply decomposition121

algorithms based on the Dantzig-Wolfe or the Benders’ decomposition scheme. SCIP-SDP allows to solve mixed-integer

122
123
124

semidefinite programs, and SCIP-Jack is a solver for Steiner tree problems. Finally, the default instantiations of the UG
framework use SCIP as a base solver in order to perform branch-and-bound in parallel computing environments.

125
126

Examples of Works Using SCIP. A number of works independent of the authors of this paper have employed SCIP

127

as a research tool. Examples of such works include papers on new symmetry handling algorithms [16], branching

128
129

rules [7] and integration of machine learning with branch-and-bound based MILP solvers [48]. Further application-

130

specific algorithms have been developed based on SCIP, for example, specialized algorithms for solving electric vehicle131

routing [13] and network path selection [11] problems. Many articles employ SCIP as an MINLP solver for problems

132such as hyperplanes location [9], airport capacity extension, fleet investment, and optimal aircraft scheduling [15],

133
134

cryptanalysis problems [17], Wasserstein distance problems [12], and chance-constrained nonlinear programs [32].

135

Structure of the Paper. The paper is organised as follows. A performance evaluation of SCIP 8.0 and a comparison

136
137

of its performance to that of SCIP 7.0 is carried out in Section 2. The core solving engine is discussed in Section 3.

138

The interfaces and modeling languages are presented in Section 4. SCIP extensions that are included in the SCIP

139

Optimization Suite are discussed in Section 5, and Section 6 concludes the paper.

140

For a more detailed description of the new features introduced in SCIP Optimization Suite 8.0, and for the technical

141
142

details, we refer the reader to the SCIP Optimization Suite 8.0 release report [8].

143
144

2

PERFORMANCE OF SCIP 8.0 FOR MILP AND MINLP

145
146

In this section, we present computational experiments conducted by running SCIP without parameter tuning or147

algorithmic variations to assess the performance changes since the 7.0 release. The indicators of interest are the number

148
149
150

of solved instances, the shifted geometric mean of the number of branch-and-bound nodes (shift 100 nodes), and theshifted geometric mean of the solving time (shift 1 second).

151
152

2.1

Experimental Setup

153
154

We use the SCIP Optimization Suite 7.0 as the baseline, including SoPlex 5.0 and PaPILO 1.0, and compare it with the155

SCIP Optimization Suite 8.0 including SoPlex 6.0 and PaPILO 2.0. Both were compiled using GCC 7.5, use Ipopt 3.12.13

156

Manuscript submitted to ACM

4Bestuzheva et al.
Table 1. Performance comparison for MILP instances

157
158
159
160
161
162
163
164
165
166
167
168
169
170

SCIP 8.0+SoPlex 6.0

SCIP 7.0+SoPlex 5.0

relative

Subsetinstancessolved

time

nodes

solved

time

nodes

time

nodes

all
affected

1708
1475

1478
1424

231.3
173.8

3311
2843

1445
1391

271.3
209.7

4107
3611

1.17
1.21

1.24
1.27

[0,tilim][1,tilim][10,tilim][100,tilim][1000,tilim]
diff-timeouts
both-solved

1529
1470
1361
1000
437
135
1394

1478
1419
1310
949
386
84
1394

154.4
185.9
248.1
537.1
1566.22072.7
119.9

2512
2870
3612
7270
17973
19597
2048

1445
1386
1277
916
353
51
1394

184.6
223.8
303.1
702.6
2383.15062.1
133.8

3167
3647
4661
10262
31707
69354
2330

1.20
1.20
1.22
1.31
1.52
2.44
1.12

1.26
1.27
1.29
1.41
1.76
3.54
1.14

171
172
173
174

as NLP subsolver built with the MUMPS 4.10.0 numerical linear algebra solver, CppAD 20180000.0 as algorithmic
differentiation library, and bliss 0.73 for detecting symmetry. The time limit was set to 7200 seconds in all cases.

175

The MILP instances are selected from the MIPLIB 2003, 2010, and 2017 [27] as well as the COR@L [37] instance176

sets and include all instances solved by SCIP 7.0 with at least one of five random seeds or solved by SCIP 8.0 with at

177
178
179

least one of five random seeds; this amounts to 347 instances. The MINLP instances are similarly selected from the
MINLPLib1 with newly solvable instances added to the ones solved by SCIP 7.0 for a total of 113 instances.

180

All performance tests were run on identical machines with Intel Xeon CPUs E5-2690 v4 @ 2.60GHz and 128GB in

181

RAM. A single run was carried out on each machine in a single-threaded mode. Each optimization problem was solved

182
183
184

with SCIP using five different seeds for random number generators. This results in a testset of 565 MINLPs and 1735
MILPs. Instances for which the solver reported numerically inconsistent results are excluded from the presented results.

185
186
187
188

2.2

MILP Performance

Results of the performance runs on MILP instances are presented in Table 1. The “affected” subset contains instances

189

for which the two solver versions show different numbers of dual simplex iterations. Instances in the subsets [𝑡, tilim]

190

were solved by at least one solver version within the time limit and took least 𝑡 seconds to solve with at least one

191

version. “both-solved” and “diff-timeouts” are the subsets of instances that can be solved by both versions and by exactly

192
193
194

one version, respectively. “relative” shows the ratio of the shifted geometric mean between the two versions.
The changes introduced with SCIP 8.0 improved the performance on MILPs both in terms of number of solved

195

instances and time. The improvement is more limited on ‘both-solved’ instances that were solved by both solvers, for196

which the relative improvement is only of 12 %. This indicates that the overall speedup is more due to newly solved

197
198

instances than to improvement on instances that were already solved by SCIP 7.0.

199
200
201
202

2.3

MINLP PerformanceWith the major revision of the handling of nonlinear constraints, the performance of SCIP on MINLPs has changed

203

considerably compared to SCIP 7.0. The results are summarized in Table 2. More instances are solved by SCIP 8.0 than204

by SCIP 7.0, and SCIP 8.0 solves the instances for each of these subsets with a shorter shifted geometric mean time.

205

On the 386 instances solved by both versions, SCIP 8.0 requires fewer nodes and less time. The number of instances

206
207

1 https://www.minlplib.org

208

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0

5Table 2. Performance comparison for MINLP

209
210
211
212
213
214
215
216
217
218
219
220
221
222

SCIP 8.0+SoPlex 6.0

SCIP 7.0+SoPlex 5.0

relative

Subsetinstancessolved

time

nodes

solved

time

nodes

time

nodes

all
affected

558
487

454
438

39.1
23.5

2427
1748

435
419

45.7
28.4

1845
1456

1.17
1.21

0.76
0.83

[0,tilim][1,tilim][10,tilim][100,tilim][1000,tilim]
diff-timeouts
both-solved

503
375
293
195
153
117
386

454
326
244
146
104
68
386

21.7
56.1
121.6
307.6
466.9
451.4
8.2

1585
3994
7450
14204
23425
29142
609

435
307
225
127
85
49
386

25.9
71.0
169.3
433.9
565.3
461.8
10.4

1326
3113
5393
6696
8382
6275
806

1.19
1.27
1.39
1.41
1.21
1.02
1.27

0.84
0.78
0.72
0.47
0.36
0.22
1.32

223
224
225

solved by only one of the two versions (diff-timeouts) is much higher than reported in previous release reports with226

similar experiments, with 68 instances solved only by SCIP 8.0 and 49 instances solved only by SCIP 7.0. A performance227

evaluation that focuses only on the changes in handling nonlinear constraints is given in Section 3.1.5.

228
229
230

3

231

This section presents the core solving engine, which includes the CIP solver SCIP, the MILP presolving library PaPILO,

232
233

THE CORE SOLVING ENGINE

and the LP solver SoPlex. It discusses SCIP’s MINLP framework in Section 3.1, which was completely reworked in the234

8.0 release, and demonstrates the possibilities for implementing user’s own methodsusing the examples of two areas

235

that saw improvement with the 8.0 release, namely symmetry handling and primal heuristics in Sections 3.2 and 3.3.

236

The full list of new features introduced in SCIP 8.0 is the following: a new framework for handling nonlinear

237
238

constraints, symmetry handling on general variables and improved orbitope detection, a new separator for mixing cuts,239

improvements to decomposition-based heuristics, the option to apply the mixed integer rounding procedure when240

generating optimality cuts in the Benders’ decomposition framework, a new plugin type that enables users to include

241

their own cut selection rules into SCIP, and several technical improvements.

242
243
244

Further, the section provides an overview of the presolving library PaPILO and the LP solver SoPlex in Sections 3.4
and 3.5, and presents the new dual postsolving feature in PaPILO, which allowed for it to be integrated into SoPlex.

245
246

3.1

SCIP’s New MINLP Framework

247
248

A new framework for handling nonlinear constraints was introduced with the SCIP 8.0 release. The main motivation for249

this change is twofold: First, it aims at increasing the reliability of the solver and alleviating numerical issues that arose

250

from problem reformulations. Second, the new design of the nonlinear framework reduces the ambiguity of expression

251
252
253

and structure types by implementing different kinds of plugins for low-level expressions that define expressions, andhigh-level structures that add functionality for particular, often overlapping structures.

254

The main components of the new framework are the following: plugins representing expressions; a reimplemen-

255

tation of the constraint handler for nonlinear constraints, cons_nonlinear; nonlinear handler plugins that provide

256
257

functionality for high-level structures; a revision of the primal heuristic that solves NLP subproblems; revised interfaces

258

to NLP solvers; and revised interface to an automatic differentiation library. Moreover, SCIP 8.0 contains cutting plane259

separators that work on nonlinear structures and interact with cons_nonlinear.

260

Manuscript submitted to ACM

6Bestuzheva et al.

261

3.1.1 New Expressions Framework. Algebraic expressions are well-formed combinations of constants, variables, and262

various algebraic operations such as addition, multiplication, exponentiation, that are used to describe mathematical

263
264
265
266
267
268
269

functions. In SCIP, they are represented by a directed acyclic graph with nodes representing variables, constants, andoperators and arcs indicating the flow of computation.
With SCIP 8.0, the expression system has been completely rewritten. Proper SCIP plugins, referred to as expression
handlers, are now used to define all semantics of an operator. These expression handlers support more callbacks thanwhat was available for user-defined operators before. Furthermore, much ambiguity and complexity is avoided by270

adding expression handlers for basic operations only. High-level structures such as quadratic functions can still be271

recognized, but are no longer made explicit by a change in the expression type.

272
273
274

3.1.2 New Handler for Nonlinear Constraints. For SCIP 8.0, the constraint handler for nonlinear constraints, cons_nonlinear,275

has been rewritten and constraint handlers for quadratic, second-order cone, absolute power, and bivariate constraints

276
277

have been removed. Some functionalities of the removed constraint handlers have been reimplemented in other plugins.

278

An initial motivation for rewriting cons_nonlinear was a numerical issue which was caused by explicit constraint279

reformulation in earlier versions. Such a reformulation can lead to a difference in constraint violation estimation in the280

original and reformulated problems and, in particular, to a solution being feasible for the reformulated problem and

281
282

infeasible for the original problem. For example, this occurs in a problem where the constraint exp(ln(1000) +1+𝑥 𝑦) ≤ 𝑧

283

is reformulated as exp(𝑤) ≤ 𝑧, ln(1000) + 1 + 𝑥 𝑦 = 𝑤 . On the MINLPLib library, this issue occurred for 7% of instances.

284

The purpose of the reformulation is to enable constructing a linear relaxation. In this process, nonlinear functions

285

are approximated by linear under- and overestimators. Since the formulas that are used to compute these estimators are

286
287
288

only available for “simple” functions, new variables and constraints were introduced to split more complex expressions
into adequate form [64, 70].

289

A trivial attempt to solve the issue of solutions not being feasible in the original problem would have been to add a

290feasibility check before accepting a solution. However, if a solution is not feasible, actions to resolve the violation of

291
292

original constraints need to be taken, such as a separating hyperplane, a domain reduction, or a branching operation.

293

Since the connection from the original to the presolved problem was not preserved, it would not have been clear which294

operations on the presolved problem would help best to remedy the violation in the original problem.

295
296
297

Thus, the new constraint handler aims to preserve the original constraints by applying only transformations that, inmost situations, do not relax the feasible space when taking tolerances into account. The reformulations that were298

necessary for the construction of a linear relaxation are not applied explicitly anymore, but handled implicitly by299

annotating the expressions that define the nonlinear constraints. Another advantage of this approach is a clear distinction

300

between the variables that were present in the original problem and the variables added for the reformulation. With

301
302
303

this information, branching is avoided on variables of the latter type. Finally, it is now possible to exploit overlapping
structures in an expression simultaneously.

304
305
306

3.1.3 Extended Formulations. Consider problems of the form (1), where the set of nonlinear constraints is non-empty,

307

and some constraints may be nonconvex. SCIP solves such problems to global optimality via a spatial branch-and-bound308

algorithm. Important parts of the algorithm are presolving, domain propagation, linear relaxation, and branching. For

309

domain propagation and linear relaxation, extended formulations are used which are obtained by introducing slack

310
311
312

variables and replacing sub-trees of the expressions that define nonlinear constraints by auxiliary variables.
Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0
313
314
315
316

These extended formulations have the following form:
min 𝑐 ⊤𝑥,s.t. ℎ𝑖 (𝑥, 𝑤𝑖+1, . . . , 𝑤𝑚 ) = 𝑤𝑖 ,

317
318
319
320

7

𝑖 = 1, . . . , 𝑚,

(MINLPext )I𝑥 ≤ 𝑥 ≤ 𝑥, 𝑤 ≤ 𝑤 ≤ 𝑤, 𝑥 I ∈ Z .
Here, 𝑤 1, . . . , 𝑤𝑚 are slack variables, and ℎ𝑖 B 𝑔𝑖 for 𝑖 = 1, . . . , 𝑚. For each function ℎ𝑖 , subexpressions 𝑓 may be321replaced by new auxiliary variables 𝑤𝑖 ′ , 𝑖 ′ > 𝑚, and new constraints ℎ𝑖 ′ (𝑥) = 𝑤𝑖 ′ with ℎ𝑖 ′ B 𝑓 are added. For the latter,

322

subexpressions may be replaced again. The result is referred to by ℎ𝑖 (𝑥, 𝑤𝑖+1, . . . , 𝑤𝑚 ) for any 𝑖 = 1, . . . , 𝑚. That is, to323

simplify notation, 𝑤𝑖+1 is used instead of 𝑤 max(𝑖,𝑚)+1 .

324
325
326

Example of an Extended Formulation. Consider constraint log(𝑥) 2 + 2 log(𝑥) 𝑦 + 𝑦 2 ≤ 4. SCIP may replace log(𝑥)327

by an auxiliary variable 𝑤 2 , since this results in a quadratic form 𝑤 22 + 2𝑤 2𝑦 + 𝑦 2 , which is both bivariate and convex,

328

the former being well suited for domain propagation and the latter being beneficial for linearization. Therefore, the329

following extended formulation may be constructed:

330
331
332
333

ℎ 1 (𝑥, 𝑦, 𝑤 2 ) B (𝑤 2 ) 2 + 2𝑤 2𝑦 + 𝑦 2 = 𝑤 1,
ℎ 2 (𝑥, 𝑦) B log(𝑥) = 𝑤 2, 𝑤 1 ≤ 4.

334
335

3.1.4 Structure Handling. The construction of extended formulations is based on the information on what algorithms

336

are available for analyzing expressions of a specific structure. Following the spirit of the plugin-oriented design of337

SCIP, these algorithms are added as separate plugins, referred to as nonlinear handlers. Nonlinear handlers can detect

338
339

structures in expressions and provide domain propagation and linear relaxation algorithms that act on these structures.

340

Unlike other plugins in SCIP, nonlinear handlers are managed by cons_nonlinear and not the SCIP core.

341

Nonlinear handlers for the following expression types are available in SCIP: quadratic expressions defined as sums

342

where at least one term is either a product of two expressions or a square expression, bilinear expressions, convex and

343
344

concave expressions, quotient expressions of the form (𝑎𝑦1 + 𝑏)/(𝑐𝑦2 + 𝑑) + 𝑒, and expressions defined in terms of semi-

345

continuous variables. The second-order cone (SOC) nonlinear handler provides separation for SOC constraints. Finally,346

the default nonlinear handler ensures that there always exist domain propagation and linear under/overestimation

347

routines for an expression and employs callbacks of expression handlers to provide the necessary functionalities.

348
349

Additional structures can be recognized for generating cutting planes to strengthen LP relaxations. Such structures350

are handled by separator plugins. While separators are not restricted to nonlinear structures, the following separators351

were introduced in SCIP 8.0 that work on MINLPs: the Reformulation-Linearization technique (RLT) [4–6] separator352

adds RLT cuts for bilinear products and can additionally reveal linearized products between binary and continuous

353
354

variables; the principal minor separator works on a matrix 𝑋 = 𝑥𝑥 ⊤ , where entries 𝑋𝑖 𝑗 represent auxiliary variables355

corresponding to 𝑥𝑖 𝑥 𝑗 , and enforces that principle 2 × 2 minors are PSD; and the intersection cuts separator for rank-1

356

constraints (disabled by default) adds cuts derived from the condition that any 2 × 2 minor of 𝑋 has determinant 0.

357
358
359

3.1.5 Performance Impact of Updates for Nonlinear Constraints. While Section 2.3 compared the performance of SCIP

360

7.0 and SCIP 8.0, this section takes a closer look at the effect of replacing only the handling of nonlinear constraints in

361

SCIP. That is, here the following two versions of SCIP are compared:

362
363

classic: the main development branch of SCIP as of 23.08.2021; nonlinear constraints handled as in SCIP 7.0;364

Manuscript submitted to ACM

8365

Bestuzheva et al.
Table 3. Comparison of performance of SCIP with classic versus new handling of nonlinear constraints on MINLPLib.

366
367

Subset368
369

instances

all

5034

clean

4839

370
371
372
373
374
375

metricclassicnew

both

solution infeasible
failedsolvedtime limit
memory limit
fastestmean timemean nodes

481
143
2929
1962
0
3733
75.9s
2543

49
70
3131
1833
0
3637
70.3s
2601

20
18
2742
1598
0
2531

376
377
378
379
380
381

new: as classic, but with the handling of nonlinear constraints replaced as detailed in this section and symmetry382

detection extended to handle nonlinear constraints (see Section 3.2).

383
384
385

SCIP has been build with GCC 7.5.0 and uses PaPILO 1.0.2, bliss 0.73, CPLEX 20.1.0.1 as LP solver, Ipopt 3.14.4,

386

CppAD 20180000.0 and Intel MKL 2020.4.304 for linear algebra (LAPACK). Ipopt uses the same LAPACK and HSL MA27387

as linear solver. All runs are carried out on machines with Intel Xeon CPUs E5-2660 v3 @ 2.60GHz and 128GB RAM in388

a single-threaded mode. A time limit of one hour, a memory limit of 100000MB, an absolute gap tolerance of 10 −6 , and

389
390

a relative gap tolerance of 10 −4 are set. All 1678 instances of MINLPLib (version 66559cbc from 2021-03-11) that can be391

handled by both versions are used. Note that MINLPLib is not designed to be a benchmark set, since, for example, some392

models are overrepresented. For each instance, two additional runs were conducted where the order of variables and

393
394

constraints were permuted. Thus, in total 5034 jobs were run for each version.

395

Table 3 summarizes the results. A run is considered as failed if the reported primal or dual bound conflicts with best396

known bounds for the instance, the solver aborted prematurely due to a fatal error, or the solver did not terminate at397

the time limit. Runs where the final solution is not feasible are counted separately. With the new version, for much

398
399

fewer instances the final incumbent is not feasible for the original problem, that is, the issue discussed in Section 3.1.2

400

has been resolved. For the remaining 49 instances, typically small violations of linear constraints or variable bounds

401

occur. Furthermore, the reduction in “failed” instances by half shows that the new version is more robust regarding the402

computation of primal and dual bounds. Finally, the new version solves about 400 additional instances in comparision

403
404
405

to the classic one, but also no longer solves about 200 instances within the time limit.
Subset “clean” refers to all instances where both versions did not fail, i.e., either solved to optimality or stopped due

406

to the time limit. We count a version to be “fastest” on an instance if it is not more than 25% slower than the other407

version. Mean times were computed as explained in the beginning of Section 2. Due to the increase in the number of

408
409
410

solved instances, a reduction in the mean time with the new version on subset “clean” can be observed, even though
the new version is fastest on less instances than the classic one.

411

Figure 1 shows performance profiles that compare both versions w.r.t. the time to solve an instance and the gap at

412

termination. The time comparison visualizes what has been observed in Table 3: the new version solves more instances,

413
414

but can be slower. The gap comparison shows that on instances that are not solved, often the new version produces a415

smaller optimality gap than the classic version.

416

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.04179
Gap at termination

Time to solve

418
419
420

#instances

421
422
423
424
425
426
427
428

5,000
4,500
4,000
3,500
3,000
2,500
2,000
1,500
1,000
500
100

429

classic
new

101

102

5,000
4,500
4,000
3,500
3,000
2,500
2,000
1,500
1,000
500
100

time factor to best (𝜏)430classic
new

101

102

gap factor to best (𝜏)

431
432
433
434

Fig. 1. Performance profiles with classic versus new handling of nonlinear constraints, showing the number of instances for which thecorresponding version was at most 𝜏 times worse (regarding time (left) or gap at termination (right)) than the best of both versions.
For the time plot, instances that were solved to optimality are considered. For the gap plot, instances that did not fail are considered.

435
436
437

3.2

438

Symmetries are known to have an adverse effect on the performance of MI(N)LP solvers due to symmetric subproblems

439
440
441

Improvements in Symmetry Handling

being treated repeatedly without providing new information to the solver. Since detecting all symmetries is N Phard [41], SCIP only detects symmetries that keep the formulation invariant.

442

SCIP’s symmetry handling framework can be used both as a black box and research tool. In the black box approach,

443

SCIP automatically detects and handles symmetries. If symmetries are known, users can tell SCIP about them by adding

444
445

specialized constraints. Customized code can include such constraints via API functions, but also black box SCIP can be

446

informed about symmetries via parsing them from files in SCIP’s CIP format. Moreover, SCIP facilitates research on

447

symmetries as it stores all symmetry information centrally in the symmetry propagator and provides implementations

448

of basic symmetry operations such as stabilizer computations.

449
450

For a permutation 𝛾 of the variable index set {1, . . . , 𝑛} and a vector 𝑥 ∈ R𝑛 , we define 𝛾 (𝑥) = (𝑥𝛾 −1 (1) , . . . , 𝑥𝛾 −1 (𝑛) ).

451

We say that 𝛾 is a symmetry of (1) if the following holds: 𝑥 ∈ R𝑛 is feasible for (1) if and only if 𝛾 (𝑥) is feasible, and 𝑐 ⊤𝑥 =452

𝑐 ⊤𝛾 (𝑥). The set of all symmetries forms a group Γ, the symmetry group of (1). If Γ is a product group Γ = Γ1 ⊗ · · · ⊗ Γ𝑘 ,453

the variables affected by one factor of Γ are not affected by any other factor. In this case, SCIP can apply different

454
455

symmetry handling methods for each factor. The sets of all variables affected by a single factor are called components.

456

SCIP 7.0 was only able to handle symmetries of binary variables in MILPs using two paradigms: a constraint-based457

approach or the pure propagation-based approach orbital fixing [39, 40, 46]. For a symmetry 𝛾, the constraint-based

458

approach enforces that the variable vector 𝑥 is lexicographically not smaller than 𝛾 (𝑥). This is implemented via three

459
460

different constraint handler plugins. For single permutations 𝛾, the symresack and orbisack constraint handlers use

461

separation and propagation [28] techniques for enforcing the lexicographic requirement, also c.f. [31]. Additionally, if

462

an entire factor Γ𝑖 of Γ has a special structure, the orbitope constraint handler applies specialized techniques [21].

463
464
465

SCIP 8.0 extends the symmetry handling framework. First, it allows to detect symmetries in MINLPs [72]. Second, in
SCIP 8.0, symmetries of general variables can be handled by inequalities derived from the Schreier-Sims table (SST466

cuts) [36, 54]. These inequalities are based on a list of leaders ℓ1, . . . , ℓ𝑘 together with suitably defined orbits 𝑂 1, . . . , 𝑂𝑘 ,467

leading to inequalities 𝑥 ℓ𝑖 ≥ 𝑥 𝑗 , 𝑗 ∈ 𝑂𝑖 , 𝑖 ∈ {1, . . . , 𝑘 }. Users have a high degree of flexibility to control the selection of468

Manuscript submitted to ACM

10Bestuzheva et al.

469

orbits and can thus select the most promising symmetry handling strategy. Third, orbitope detection has been extended

470

to also detect suborbitopes, i.e., parts of the symmetry group that allow to apply orbitopes. Since adding suborbitopes

471
472
473

did not turn out to always be beneficial, SCIP adds suborbitopes according to a strategy that can combine suborbitopes
and SST cuts; adding SST cuts can be controlled by a user via parameters.

474

Furthermore, SCIP 8.0 contains improvements of previously available methods. First, if orbisack constraints interact475with set packing or partitioning constraints in a certain way, they are automatically upgraded to orbitopes. This upgrade

476
477

has been made more efficient. Second, the running time of the separation routine of cover inequalities for symresacks

478

has been improved from quadratic to linear by using the observation from [28] that minimal cover inequalities for479

symresacks can be separated by merging connected components of an auxiliary graph. The new implementation exploits

480

that its connected components are either paths or cycles. Finally, propagation routines of the symresack and orbisack

481
482

constraint handler now find all variable fixings that can be derived from local variable bound information.

483
484

3.3

Primal Decomposition Heuristics

485
486

Most MILPs have sparse constraint matrices for which a (bordered) block-diagonal form might be obtained by permuting

487

the rows/columns of the matrix. Identifying such a form allows for potentially rendering large-scale complex problems

488

considerably more tractable. Solution algorithms or heuristics can be designed exploiting the underlying structure and

489
490
491
492
493
494

yielding smaller, easier problems. In this sense, a so-called decomposition identifies subsets of rows and columns thatare only linked to each other via a set of linking rows and/or linking columns, but are otherwise independent.
A decomposition consisting of 𝑘 ∈ N blocks is a partition D B (𝐷 row, 𝐷 col ) with 𝐷 row B (𝐷 1row, . . . , 𝐷𝑘row, 𝐿 row ), 𝐷 col B(𝐷 1col, . . . , 𝐷𝑘col, 𝐿 col ) of the rows/columns of the constraint matrix 𝐴 into 𝑘 + 1 pieces each, whereby it holds for all

495

𝑖 ∈ 𝐷𝑞row, 𝑗 ∈ 𝐷𝑞colthat 𝑎𝑖,𝑗 ≠ 0 implies 𝑞 1 = 𝑞 2 . Rows 𝐿 row and columns 𝐿 col , which may be empty, are called linking
1
2

496

rows and columns, respectively.

497

In general, there is no unique way to decompose an MILP, and different decompositions might lead to different solver

498

behaviors. Users might be aware of decompositions and know which are most useful for a specific problem. Therefore,

499
500

since version 7.0 it is possible to pass user decompositions to SCIP [21]. A decomposition structure can be created using

501

the SCIP API, assigning labels to variables and/or constraints, and calling automatic label computation procedures if

502

necessary. Alternatively, SCIP also provides a file reader for decompositions in constraints.

503
504
505

In SCIP 7.0, the Benders decomposition framework and the heuristic Graph Induced Neighborhood Search wereextended to exploit user-provided decompositions, and a first version of the heuristic Penalty Alternating Direction

506

Method (PADM) [25, 55] was introduced. SCIP 8.0 comes with an improvement of PADM and provides another507

decomposition heuristic Dynamic Partition Search (DPS) [8].

508
509
510
511

Improvement of Penalty Alternating Direction Method. PADM splits an MINLP into several subproblems according toa given decomposition D with linking variables only, whereby the linking variables get copied and the differences

512

are penalized. Then the subproblems are alternatingly solved. For faster convergence, the objective function of each513

subproblem has been replaced by a penalty term, and this replacement can lead to arbitrarily bad solutions. Therefore,

514

PADM has been extended by the option to improve a found solution by reintroducing the original objective function.

515
516
517

Dynamic Partition Search. The new primal construction heuristic DPS requires a decomposition with linking con-518

straints only. The linking constraints and their sides are split by introducing vectors 𝑝𝑞 ∈ R𝐿

519

𝑞 ∈ {1, . . . , 𝑘 }, where R𝐿

520

Manuscript submitted to ACM

row

row

for each block

denotes the space of vectors with components indexed by 𝐿 row , and requiring that theEnabling Research through the SCIP Optimization Suite 8.0
521

following holds:

522

𝑘
∑︁

523
524
525
526
527

11

(2)

𝑝𝑞 = 𝑏 [𝐿row ] .

𝑞=1

To obtain information on subproblem infeasibility and speed up the solving process, the objective function is replaced
by a weighted sum of slack variables 𝑧𝑞 ∈ R𝐿+

row

row

. For penalty parameter 𝜆 ∈ R𝐿>0 , each subproblem 𝑞 has the formmin 𝜆 ⊤𝑧𝑞 ,

528
529

s.t. 𝐴 [𝐷 row ,𝐷 col ] 𝑥 [𝐷 col ] ≥ 𝑏 [𝐷𝑞row ] ,
𝑞
𝑞
𝑞

530
531

𝑥 𝑖 ≤ 𝑥𝑖 ≤ 𝑥 𝑖

for all 𝑖 ∈ N ∩ 𝐷𝑞col,𝑥𝑖 ∈ Z

for all 𝑖 ∈ I ∩ 𝐷𝑞col,

532
533
534

(3)

𝐴 [𝐿row ,𝐷 col ] 𝑥 [𝐷 col ] + 𝑧𝑞 ≥ 𝑝𝑞 ,

535
536

𝑧𝑞 ∈ R𝐿+

𝑞

𝑞
row

.

537
538

From (3), it is apparent that the correct choice of 𝑝𝑞 plays a central role. For this reason, we refer to (𝑝𝑞 )𝑞 ∈ {1,...,𝑘 } as539

a partition of 𝑏 [𝐿row ] . The method starts with an initial partition fulfilling (2). Then it is checked whether this partition

540

will lead to a feasible solution by solving 𝑘 independent subproblems (3) with fixed 𝑝𝑞 . If the current partition does

541
542
543

not correspond to a feasible solution, then the partition gets updated, so that (2) still holds. These steps are repeated.
Similarly to PADM, it is possible to improve the found solution by reoptimizing with the original objective function.

544
545

3.4 PaPILO

546
547

The C++ library PaPILO provides presolving routines for (MI)LP problems and was introduced with the SCIP Opti-

548

mization Suite 7.0 [21]. PaPILO can be integrated into MILP solvers or used as a standalone presolver. As a standalone549

presolver it provides presolving and postsolving routines. Hence, it can be used to a) provide presolving for new solving

550
551

methods and b) generate presolved instances so that different solvers can be benchmarked independently of their own

552

presolvers. Thus, the performance/behavior of the actual solver can be evaluated and compared more precisely.

553

PaPILO’s transaction-based design allows presolvers to run in parallel without requiring expensive copies of the554

problem and without special synchronizations. Instead of applying results immediately, presolvers return their reductions

555
556

to the core, where they are applied in a deterministic, sequential order. Validity of every reduction to the modified

557

problem is checked to avoid applying conflicting reductions.

558

Presolving deletes variables from the original problem by fixing, substituting, and aggregating variables. After solving

559

the reduced problem, its solution does not contain any information on missing variables. To restore the solution values

560
561

of these variables and obtain a feasible solution of the original problem, corresponding data needs to be stored during

562

the presolving process. The process of recalculating the original solution from the reduced one is called postsolving

563

or post-processing [3]. Until version 1.0.2, PaPILO supported only postsolving primal solutions for LPs. In the latest

564

version, PaPILO supports postsolving also for dual solutions, reduced costs, slack variables of the constraints, and the

565
566

basic status of the variables and constraints for the majority of the LP presolvers.

567
568

3.5 SoPlex

569
570

SoPlex is a simplex-based LP solver and an essential part of the optimization suite, since is the default LP-solver for

571

SCIP. In addition to all the essential features of a state-of-the-art LP solver such as scaling, exploitation of sparsity,

572

Manuscript submitted to ACM

12Bestuzheva et al.

573

or presolving, SoPlex also supports an option for 80bit extended precision and an iterative refinement algorithm to574

produce high-precision solutions. This enables SoPlex to also compute exact rational solutions to LPs, using either

575
576

continued fraction approximations or a symbolic LU factorization.

577

The support of postsolving of dual LP solutions and basis information in PaPILO makes it possible to integrate

578

PaPILO fully as a presolving library into SoPlex. In version 6.0 of SoPlex, PaPILO is available as an additional option

579

for presolving. The previous presolving implementation continues to be the default.

580
581
582
583
584
585

4

MODELING LANGUAGES AND INTERFACES

There are many interfaces to SCIP from different programming and modeling languages. These interfaces allow users
to programmatically call SCIP with an API close to the C one or leverage a higher-level syntax.

586

The AMPL interface has been rewritten and moved to the main SCIP library and executable. With the SCIP Opti-

587

mization Suite 8.0, there exists a C wrapper for SoPlex, updated GAMS interfaces for SoPlex and SCIP, a Julia package

588

SCIP.jl, a basic Java interface JSCIPOpt, a new Matlab interface for SCIP 8.0 and SCIP-SDP based on the OPTI Toolbox

589
590

by Jonathan Currie, and the Python interface PySCIPOpt which can now also be installed as a Conda package.

591

The modeling language Zimpl allows for MI(N)LPs to be written and translated into some file formats supported by592

SCIP. Zimpl 3.5.0 allows quadratic objective functions in addition to previously supported linear objective functions,593

and can write suitable instances as Quadratic Unconstrained Binary Optimization problems.

594
595

5

EXTENSIONS

596
597
598
599

5.1

The GCG Decomposition Solver

SCIP allows implementing tailored decomposition-based algorithms. Complementary to this, GCG turns SCIP into

600

a generic decomposition-based solver for MILPs. While GCG’s focus is on Dantzig-Wolfe reformulation (DWR) and

601

Lagrangian decomposition, Benders decomposition (BD) is also supported. The philosophy behind GCG is that

602
603
604

decomposition-based algorithms can be routinely applied to MILPs without the user’s interaction or even knowledge.
To this end, GCG automatically detects a model structure that admits a decomposition and performs the corresponding605

reformulation. This results in a master problem and one or several subproblems, which are usually formulated as

606

MILPs. Based on the reformulation, the linear relaxation in every node is solved by column generation (in the DWR

607case) and Benders cut generation (in the BD case). GCG features primal heuristics and separation of cutting planes,

608
609

several of which are adapted from SCIP, but some are tailored to the decomposition situation in which both an original610

and a reformulated model are available. As a research tool, GCG can be used to quickly assess the potential of a611

decomposition-based algorithm for any problem for which a compact MILP formulation is available. This allows

612

evaluating the performance of an algorithmic idea with a single generic implementation, but across many different

613
614
615
616

applications. In what follows, we describe some enhancements in the GCG 3.5 release.
5.1.1 Detection Loop Refactoring. Decomposition-based algorithms rely on model structures, cf. Section 3.3. For

617

automatic identification of such structures, GCG features a modular detection loop. Detectors iteratively assign roles

618

like “master” or “block” to variables and/or constraints. This way, usually many different potential decompositions

619

are found. We refer to the SCIP Optimization Suite 6.0 release report [26] for a more detailed overview. Detectors are

620
621

implemented as plugins such that new ones can be added conveniently. In every round, each detector works on existing622(but possibly empty) partial or complete decompositions. An empirically very successful detection concept builds on623

the classification of constraints and variables, which is performed prior to the actual detection process, using classifiers.

624

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0

13

625

5.1.2 Branching. In GCG, two general branching rules are implemented (branching on original variables [71] and626

Vanderbeck’s generic branching [69]) as well as one rule that applies only to set partitioning master problems (Ryan

627
628

and Foster branching [53]). While these rules differ significantly, the general procedure has two common stages: First,

629

one determines the set of candidates we could possibly branch on (called the branching rule). Second, the branching

630

candidate selection heuristic selects one of the candidates. GCG previously contained pseudo cost, most fractional, and

631
632
633
634
635

random branching as selection heuristics for original variable branching, and first-index branching for Ryan-Foster andVanderbeck’s generic branching. In GCG 3.5, new strong branching-based selection heuristics are added [24].
5.1.3 Python Interface. With GCG 3.5 we introduce PyGCGOpt which extends SCIP’s existing Python interface [38]636

for GCG and is distributed independently from the optimization suite2 . All existing functionality for MILP modeling is637

inherited from PySCIPOpt; therefore, any MILP modeled in Python can be solved with GCG without additional effort.

638

The interface supports specifying custom decompositions and exploring automatically detected decompositions, and

639
640
641
642

plugins for detectors and pricing solvers can be implemented in Python.
5.1.4 Visualization Suite. Visualizations of algorithmic behavior can yield understanding and intuition for interesting643

parts of a solving process. With GCG 3.5, we include a Python-based visualization suite that offers visualization scripts

644

to show processes and results related to detection, branching, or pricing, among others. We highlight two features:

645(1) Reporting functionality: A decomposition report offers an overview of all decompositions that GCG found for a646

single run. For different runs, GCG 3.5 offers two reports: A testset report shows data and graphics for each647

single run of one selected test set. A comparison report allows to compare two or more runs on the same test set.

648(2) Jupyter notebook: data produced for the reports can be read, cleaned, filtered, and visualized interactively.

649
650
651

5.2

SCIP-SDP

652
653

SCIP-SDP is an MISDP solver and a platform for implementing methods for solving MISDPs. It was initiated by Sonja

654

Mars and Lars Schewe [42], and then continued by Gally et al. [20] and Gally [19]. New results and methods mainly

655

concerning presolving and propagation are presented in [43]. SCIP-SDP features interfaces to SDP-solvers DSDP, Mosek,

656
657

and SDPA.

658

SCIP-SDP implements an SDP-based branch-and-bound method, which solves a continuous SDP relaxation in each659

node. It incorporates plugins such as primal heuristics, presolving and propagation methods, and file readers. There is660

also an option to solve LP relaxations in each node of the branch-and-bound tree and generate eigenvector cuts, see

661
662

Sherali and Fraticelli [56]. This is sometimes faster than solving SDPs in every node. These two options can also be run

663

concurrently if the parallel interface TPI of SCIP is used. There also is a Matlab interface to SCIP-SDP.

664
665
666

Moreover, SCIP-SDP can handle rank-1 constraints, that is, the requirement that the resulting matrix 𝐴(𝑦) in (??) has
rank 1. For such a constraint, quadratic constraints are added, modeling that all 2 × 2-minors of 𝐴(𝑦) are zero [14].

667Before we present some computational results, let us add some words of caution. Although SCIP-SDP is numerically668

quite robust, accurately solving SDPs is more demanding than solving LPs. This can lead to wrong results on some669

instances3 , and the results often depend on the tolerances. Moreover, the SDP-solvers use relative tolerances, while

670

SCIP-SDP uses absolute tolerances. Finally, for Mosek, we use a slightly tighter feasibility tolerance than in SCIP-SDP.

671
672

Table 4 shows a comparison between SCIP-SDP 3.2 and 4.0 on the same testset as used by Gally et al. [20], which

673

consists of 194 instances; the changes between SCIP-SDP 4.0 and 3.2 are presented in more detail in [8, 43]. Reported are

674

2 https://github.com/scipopt/PyGCGOpt

675

3 For instance, in seldom cases, the dual bound might exceed the value of a primal feasible solution.

676

Manuscript submitted to ACM

14Bestuzheva et al.
Table 4. Performance comparison of SCIP-SDP 4.0 vs. SCIP-SDP 3.2

677
678
679
680
681

SCIP-SDP 3.2
SCIP-SDP 4.0# opt# nodestime [s]

185
187

617.3
497.3

42.9
26.6

682
683
684
685
686

the number of optimally solved instances, as well as the shifted geometric means of the number of processed nodes andthe CPU time in seconds. We use Mosek 9.2.40 for solving the continuous SDP relaxations. The tests were performed on

687

a Linux cluster with 3.5 GHz Intel Xeon E5-1620 Quad-Core CPUs, having 32 GB main memory and 10 MB cache. All

688

computations were run single-threaded and with a timelimit of one hour.

689
690
691

As can be seen from the results, SCIP-SDP 4.0 is considerably faster than SCIP-SDP 3.2, but we recall that we haverelaxed the tolerances. Nevertheless, we conclude that SCIP-SDP has significantly improved since the last version.

692
693

5.3

694

Given an undirected, connected graph, edge costs and a set of terminal vertices, the Steiner tree problem in graphs (SPG)

695
696
697

SCIP-Jack: Solving Steiner Tree and Related Problems

asks for a tree of minimum weight that covers all terminals. The SPG is a fundamental N P-hard problem [33] and oneof the most studied problems in combinatorial optimization.

698

SCIP-Jack, an exact SPG-solver, is built on the branch-and-cut framework provided by SCIP and makes extensive use

699

of its plugin-based design. At the heart of the implementation is a constraint handler that separates violated constraints,

700
701

most importantly the so-called directed Steiner cuts, which are separated by a specialized maximum-flow algorithm [49].

702

The implementation includes a variety of additional SCIP plugins, such as heuristics, propagators, branching rules and703

relaxators. Finally, the use of SCIP provides significant flexibility in the model to be solved, for example it is easily704

possible to add additional constraints. In this way, SCIP-Jack can solve not only the SPG, but also 14 related problems.

705

The SCIP Optimization Suite 8.0 contains the new SCIP-Jack 2.04 , which comes with major improvements on most

706
707

problem classes it can handle and outperforms the SPG solver by Polzin and Vahdati [47, 68], which had remained

708

unchallenged for almost 20 years, on almost all nontrivial benchmark testsets from the literature [51].

709
710
711

Figure 2 provides computational results on the instances from Tracks A and B of the PACE Challenge 2018 [10].
We use Gurobi 9.5 (Commercial), the best other solver from the PACE Challenge (SPDP [29]), and SCIP-Jack with

712

SoPlex (SCIPJ/spx) and Gurobi 9.5 (SCIPJ/grb) as LP solvers. A timelimit of one hour was set. Average times are given713

as arithmetic means with time-outs counted as one hour each. The results were obtained on Intel Xeon CPUs E3-1245

714@ 3.40 GHz with 32 GB RAM. It can be seen that SCIPJ/grb is roughly 17 times faster than SPDP, and 96 times faster

715
716
717

than Gurobi. For larger instances of the PACE 2018 benchmark, one commonly observes a run time difference of morethan six orders of magnitude between SCIP-Jack and commercial MILP solvers.

718

Considerable problem-specific improvements have been made for the prize-collecting Steiner tree problem (STP)719

and (to a lesser extent) for the maximum-weight connect subgraph problem [50, 52]. SCIP-Jack 2.0 can solve many

720
721

previously unsolved benchmark instances from both problem classes to optimality—the largest of these instances have722

up to 10 million edges. Large improvements are observed for the Euclidean STP: SCIP-Jack 2.0 is able to solve 19

723

Euclidean STPs with up to 100 000 terminals to optimality for the first time [51]. Notably, the state-of-the-art Euclidean

724

STP solver GeoSteiner 5.1 [30] could not solve any of these instances, even after one week of computation. In contrast,

725
726

SCIP-Jack 2.0 solves all of them within 12 minutes, some even within two minutes.

727

4 See also https://scipjack.zib.de.

728

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0
729

2500
Average time (seconds)

730
731
732
733
734
735
736
737

95.95x500

Solved instances
67
Commercial

738

15

Commercial
SPDP
SCIP-Jack/spx
SCIP-Jack/grb

17.63x
1.89x
176
SPDP

1.00x

198
199
SCIPJ/spx SCIPJ/grb

739
740

Fig. 2. Computational results on the 200 benchmark instances of Tracks A and B of the PACE Challenge 2018.

741
742
743
744
745
746

5.4

The UG Framework

UG is a generic framework for parallelizing solvers in a distributed or shared memory computing environment. It
was designed to parallelize state-of-the-art branch-and-bound solvers externally in order to exploit their powerful747

performance. We have developed parallel solvers for SCIP [58, 59, 61], CPLEX (not developed anymore), FICO Xpress [60],748PIPS-SBB [44, 45], Concorde5 , and QapNB [18]. Customized SCIP-based solvers such as SCIP-SDP and SCIP-Jack can be749

parallelized with minimal effort [62]. The parallel version of SCIP-Jack solved several previously unsolved instances

750
751

from SteinLib [35] by using up to 43,000 cores [63].

752

In addition to the parallelization of these branch-and-bound base solvers, UG was used to develop MAP-SVP [65],753

which is a solver for the Shortest Vector Problem (SVP), whose algorithm does not rely on branch-and-bound. For these754

applications, UG had to be adapted and modified. Especially, the success of MAP-SVP, which updated several records

755of the SVP challenge6 , motivated us to develop generalized UG, in which all solvers developed so far can be handled

756
757

by a single unified framework. This has enabled UG 1.0 to serve as the basis for the parallel frameworks CMAP-LAP

758(Configurable Massively Parallel solver framework for LAttice Problems) [66] and CMAP-DeepBKZ [67].

759
760

6

FINAL REMARKS

761
762

We discussed the functionality that the SCIP Optimization Suite offers optimization researchers, and highlighted

763

performance improvements and new functionality that was introduced in the SCIP Optimization Suite 8.0. The perfor-

764

mance comparison of SCIP 7.0 and SCIP 8.0 showed a 17 % speed-up on both the MILP and MINLP testsets. This was

765
766

followed by a discussion of some aspects of the core solving engine of the SCIP Optimization Suite. The new framework767

for handling nonlinear constraints was presented, which offers increased reliability as well as improved handling of

768

different types of nonlinearities that reduces type ambiguity and extends support for implementing the handling of

769
770
771

user-defined nonlinearities. The use of SCIP’s flexible plugin-based structure for extending the solver with user methods
was demonstrated on the examples of new symmetry handling methods and primal decomposition heuristics. The

772

framework that SCIP provides for working on these methods was explained and the relevant plugin types and other773

customization-enabling features were discussed, followed by the presentation of new methods added in SCIP 8.0.

774
775
776
777

Further, we presented extensions built around SCIP. The semidefinite programming solver SCIP-SDP and the Steiner
tree problem solver SCIP-Jack provide users of the SCIP Optimization Suite the functionality for solving more problem
classes, the decomposition solver GCG offers a different solving approach, and the solver parallelization framework UG

778

5 https://www.math.uwaterloo.ca/tsp/concorde.html

779

6 http://latticechallenge.org/svp-challenge

780

Manuscript submitted to ACM

16Bestuzheva et al.

781

enables the use of branch-and-bound solvers, and in particular SCIP, in parallel computing environments. Moreover,782

these components of the SCIP Optimization Suite demonstrate how SCIP’s features can be leveraged in creating new

783
784

research projects which can extend beyond SCIP’s standard focus and approach.

785
786

ACKNOWLEDGMENTS

787
788

The authors want to thank all previous developers and contributors to the SCIP Optimization Suite and all users that789

reported bugs and often also helped reproducing and fixing the bugs. In particular, thanks go to Suresh Bolusani, Didier

790
791

Chételat, Gregor Hendel, Gioni Mexi, Matthias Miltenberger, Andreas Schmitt, Robert Schwarz, Helena Völker, Matthias

792

Walter, and Antoine Prouvoust and the Ecole team. The Matlab interface was set up with the big help of Nicolai Simon.

793

The work for this article has been partly conducted within the Research Campus MODAL funded by the German

794

Federal Ministry of Education and Research (BMBF grant number 05M14ZAM) and has received funding from the

795
796

European Union’s Horizon 2020 research and innovation programme under grant agreement No 773897. It has also

797

been partly supported by the German Research Foundation (DFG) within the Collaborative Research Center 805, Project798

A4, and the EXPRESS project of the priority program CoSIP (DFG-SPP 1798), the German Research Foundation (DFG)799

within the project HPO-NAVI (project number 391087700).

800
801
802
803
804
805

Author Affiliations
KSENIA BESTUZHEVA, Zuse Institute Berlin, Department AIS2 T, Takustr. 7, 14195 Berlin, Germany; e-mail: bestuzheva@zib.de;
ORCID: 0000-0002-7018-7099

806

MATHIEU BESANÇON, ZIB-AIS2 T; e-mail: besancon@zib.de; ORCID: 0000-0002-6284-3033

807

WEI-KUN CHEN, School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, China; e-mail: chen-808

weikun@bit.edu.cn; ORCID: 0000-0003-4147-1346

809

ANTONIA CHMIELA, ZIB-AIS2 T; e-mail: chmiela@zib.de; ORCID: 0000-0002-4809-2958

810

TIM DONKIEWICZ, RWTH Aachen University, Lehrstuhl für Operations Research, Kackertstr. 7, 52072 Aachen, Germany; e-mail:

811
812
813

tim.donkiewicz@rwth-aachen.de; ORCID: 0000-0002-5721-3563
JASPER VAN DOORNMALEN, Eindhoven University of Technology, Department of Mathematics and Computer Science; e-mail:814

m.j.v.doornmalen@tue.nl; ORCID: 0000-0002-2494-0705

815

LEON EIFLER, ZIB-AIS2 T; e-mail: eifler@zib.de; ORCID: 0000-0003-0245-9344

816

OLIVER GAUL, RWTH Aachen University, Lehrstuhl für Operations Research, Kackertstr. 7, 52072 Aachen, Germany; e-mail:817

oliver.gaul@rwth-aachen.de; ORCID: 0000-0002-2131-1911

818

GERALD GAMRATH, ZIB-AIS2 T and I2 DAMO GmbH, Englerallee 19, 14195 Berlin, Germany; e-mail: gamrath@zib.de; ORCID:

819
820
821

0000-0001-6141-5937
AMBROS GLEIXNER, ZIB-AIS2 T and HTW Berlin; e-mail: gleixner@zib.de; ORCID: 0000-0003-0391-5903

822

LEONA GOTTWALD, ZIB-AIS2 T; e-mail: gottwald@zib.de; ORCID: 0000-0002-8894-5011

823

CHRISTOPH GRACZYK, ZIB-AIS2 T; e-mail: graczyk@zib.de; ORCID: 0000-0001-8990-9912

824

KATRIN HALBIG, Friedrich-Alexander Universität Erlangen-Nürnberg, Department of Data Science, Cauerstr. 11, 91058 Erlangen,825

Germany; e-mail: katrin.halbig@fau.de; ORCID: 0000-0002-8730-3447

826

ALEXANDER HOEN, ZIB-AIS2 T; e-mail: hoen@zib.de; ORCID: 0000-0003-1065-1651

827
828
829

CHRISTOPHER HOJNY, Eindhoven University of Technology, Department of Mathematics and Computer Science; e-mail: c.hojny@tue.nl;
ORCID: 0000-0002-5324-8996

830

ROLF VAN DER HULST, University of Twente, Department of Discrete Mathematics and Mathematical Programming, P.O. Box 217,

831

7500 AE Enschede, The Netherlands; e-mail: r.p.vanderhulst@utwente.nl

832

Manuscript submitted to ACM

Enabling Research through the SCIP Optimization Suite 8.0

17

833

THORSTEN KOCH, Technische Universität Berlin, Chair of Software and Algorithms for Discrete Optimization, Straße des 17.

834

Juni 135, 10623 Berlin, Germany, and ZIB, Department A2 IM, Takustr. 7, 14195 Berlin, Germany; e-mail: koch@zib.de; ORCID:

835
836
837

0000-0002-1967-0077
MARCO LÜBBECKE, RWTH Aachen-Lehrstuhl für OR; e-mail: marco.luebbecke@rwth-aachen.de; ORCID: 0000-0002-2635-0522

838

STEPHEN J. MAHER, University of Exeter, College of Engineering, Mathematics and Physical Sciences, Exeter, United Kingdom;839

e-mail: s.j.maher@exeter.ac.uk, ORCID: 0000-0003-3773-6882

840

FREDERIC MATTER, Technische Universität Darmstadt, Fachbereich Mathematik, Dolivostr. 15, 64293 Darmstadt, Germany; e-mail:841

matter@mathematik.tu-darmstadt.de; ORCID: 0000-0002-0499-1820

842

ERIK MÜHMER, RWTH Aachen-Lehrstuhl für OR; e-mail: erik.muehmer@rwth-aachen.de; ORCID: 0000-0003-1114-3800

843

BENJAMIN MÜLLER, ZIB-AIS2 T; e-mail: benjamin.mueller@zib.de; ORCID: 0000-0002-4463-2873

844
845
846

MARC E. PFETSCH, TU Darmstadt, Fachbereich Mathematik; e-mail: pfetsch@mathematik.tu-darmstadt.de; ORCID: 0000-0002-09477193

847

DANIEL REHFELDT, ZIB-A2 IM; e-mail: rehfeldt@zib.de; ORCID: 0000-0002-2877-074X

848

STEFFAN SCHLEIN, RWTH Aachen-Lehrstuhl für OR; e-mail: steffan.schlein@rwth-aachen.de

849

FRANZISKA SCHLÖSSER, ZIB-AIS2 T; e-mail: schloesser@zib.de

850

FELIPE SERRANO, ZIB-AIS2 T; e-mail: serrano@zib.de; ORCID: 0000-0002-7892-3951

851

YUJI SHINANO, ZIB-A2 IM; e-mail: shinano@zib.de; ORCID: 0000-0002-2902-882X

852

BORO SOFRANAC, ZIB-AIS2 T and TU Berlin; e-mail: sofranac@zib.de; ORCID: 0000-0003-2252-9469

853
854

MARK TURNER, ZIB-A2 IM and Chair of Software and Algorithms for Discrete Optimization, Institute of Mathematics, TU Berlin;855

e-mail: turner@zib.de; ORCID: 0000-0001-7270-1496

856

STEFAN VIGERSKE, GAMS Software GmbH, c/o ZIB-AIS2 T; e-mail: svigerske@gams.com

857

FABIAN WEGSCHEIDER, ZIB-AIS2 T; e-mail: wegscheider@zib.de

858

PHILIPP WELLNER; e-mail: p.we@fu-berlin.de859

DIETER WENINGER, Friedrich-Alexander Universität Erlangen-Nürnberg, Department of Data Science, Cauerstr. 11, 91058 Erlangen,

860
861
862

Germany; e-mail: dieter.weninger@fau.de; ORCID: 0000-0002-1333-8591
JAKOB WITZIG, ZIB-AIS2 T; e-mail: witzig@zib.de; ORCID: 0000-0003-2698-0767

863
864

REFERENCES

865

883

[1] T. Achterberg. 2007. Constraint Integer Programming. Dissertation. Technische Universität Berlin.
[2] Tobias Achterberg. 2009. SCIP: Solving Constraint Integer Programs. Mathematical Programming Computation 1, 1 (2009), 1–41. https://doi.org/10.
1007/s12532-008-0001-1[3] Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger. 2020. Presolve Reductions in Mixed Integer Programming.
INFORMS Journal on Computing 32, 2 (2020), 473–506. https://doi.org/10.1287/ijoc.2018.0857[4] Warren P Adams and Hanif D Sherali. 1986. A tight linearization and an algorithm for zero-one quadratic programming problems. Management
Science 32, 10 (1986), 1274–1290. https://doi.org/10.1287/mnsc.32.10.1274[5] Warren P Adams and Hanif D Sherali. 1990. Linearization strategies for a class of zero-one mixed integer programming problems. Operations
Research 38, 2 (1990), 217–226. https://doi.org/10.1287/opre.38.2.217[6] Warren P Adams and Hanif D Sherali. 1993. Mixed-integer bilinear programming problems. Mathematical Programming 59, 1 (1993), 279–305.
https://doi.org/10.1007/BF01581249[7] Daniel Anderson, Pierre Le Bodic, and Kerri Morgan. 2021. Further results on an abstract model for branching and its application to mixed integer
programming. Mathematical Programming 190, 1 (2021), 811–841.
[8] Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul,
Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst,
Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan
Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner,
Dieter Weninger, and Jakob Witzig. 2021. The SCIP Optimization Suite 8.0. Technical Report. Optimization Online. http://www.optimizationonline.org/DB_HTML/2021/12/8728.html[9] Víctor Blanco, Alberto Japón, Diego Ponce, and Justo Puerto. 2021. On the multisource hyperplanes location problem to fitting set of points.
Computers & Operations Research 128 (2021), 105124.

884

Manuscript submitted to ACM

866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882

18
885

Bestuzheva et al.

935[10] Édouard Bonnet and Florian Sikora. 2018. The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration.
In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 (LIPIcs, Vol. 115), Christophe Paul and Michal Pilipczuk (Eds.).
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 26:1–26:15. https://doi.org/10.4230/LIPIcs.IPEC.2018.26[11] Marco Casazza and Alberto Ceselli. 2021. Optimization algorithms for resilient path selection in networks. Computers & Operations Research 128(2021), 105191.
[12] Türkü Özlüm Çelik, Asgar Jamneshan, Guido Montúfar, Bernd Sturmfels, and Lorenzo Venturello. 2021. Wasserstein distance to independence
models. Journal of Symbolic Computation 104 (2021), 855–873.
[13] Alberto Ceselli, Ángel Felipe, M Teresa Ortuño, Giovanni Righini, and Gregorio Tirado. 2021. A branch-and-cut-and-price algorithm for the electricvehicle routing problem with multiple technologies. In Operations Research Forum, Vol. 2. Springer, 1–33.
[14] Chen Chen, Alper Atamtürk, and Shmuel S Oren. 2017. A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables.
Mathematical Programming 165, 2 (2017), 549–577.
[15] Stefano Coniglio, Mathias Sirvent, and Martin Weibelzahl. 2021. Airport capacity extension, fleet investment, and optimal aircraft scheduling in a
multilevel market model: quantifying the costs of imperfect markets. OR Spectrum 43, 2 (2021), 367–408.
[16] Gustavo Dias and Leo Liberti. 2021. Exploiting symmetries in mathematical programming via orbital independence. Annals of Operations Research
298, 1 (2021), 149–182.
[17] Antonio Florez-Gutierrez, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, André Schrottenloher, and Ferdinand Sibleyras. 2021. Internal
Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli. Journal of Cryptology 34, 4 (2021), 1–37.
[18] Koichi Fujii, Naoki Ito, Sunyoung Kim, Masakazu Kojima, Yuji Shinano, and Kim-Chuan Toh. 2021. Solving Challenging Large Scale QAPs. ZIB-Report
21-02. Zuse Institute Berlin.
[19] Tristan Gally. 2019. Computational Mixed-Integer Semidefinite Programming. Dissertation. TU Darmstadt.
[20] Tristan Gally, Marc E. Pfetsch, and Stefan Ulbrich. 2018. A Framework for Solving Mixed-Integer Semidefinite Programs. Optimization Methods andSoftware 33, 3 (2018), 594–632. https://doi.org/10.1080/10556788.2017.1322081[21] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona
Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger,
Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian
Wegscheider, Dieter Weninger, and Jakob Witzig. 2020. The SCIP Optimization Suite 7.0. Technical Report. Optimization Online. http://www.
optimization-online.org/DB_HTML/2020/03/7705.html.
[22] Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt, and Yuji Shinano. 2017. SCIP-Jack—a solver for STP and variants withparallelization extensions. Mathematical Programming Computation 9, 2 (2017), 231–296. https://doi.org/10.1007/s12532-016-0114-x[23] Gerald Gamrath and Marco E. Lübbecke. 2010. Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs. In Experimental
Algorithms (Lecture Notes in Computer Science, Vol. 6049), Paola Festa (Ed.). Springer Berlin Heidelberg, 239–252. https://doi.org/10.1007/978-3-64213193-6_21[24] Oliver Gaul. 2021. Hierarchical Strong Branching and Other Strong Branching-Based Branching Candidate Selection Heuristics in Branch-and-Price.
Master’s thesis. RWTH Aachen University.
[25] Björn Geißler, Antonio Morsi, Lars Schewe, and Martin Schmidt. 2017. Penalty Alternating Direction Methods for Mixed-Integer Optimization: A
New View on Feasibility Pumps. SIAM Journal on Optimization 27, 3 (2017), 1611–1636. https://doi.org/10.1137/16M1069687[26] Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny,Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel
Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegscheider,
Jonas T. Witt, and Jakob Witzig. 2018. The SCIP Optimization Suite 6.0. Technical Report. Optimization Online. http://www.optimizationonline.org/DB_HTML/2018/07/6692.html[27] A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bastubbe, T. Berthold, P.M. Christophel, K. Jarck, Th. Koch, J. Linderoth, M. Lübbecke,
H.D. Mittelmann, D. Ozyurt, T.K. Ralphs, D. Salvagnin, and Y. Shinano. 2021. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer
Programming Library. Mathematical Programming Computation 13 (2021), 443–490. https://doi.org/10.1007/s12532-020-00194-3[28] Christopher Hojny and Marc E. Pfetsch. 2019. Polytopes associated with symmetry handling. Mathematical Programming 175, 1 (2019), 197–240.
https://doi.org/10.1007/s10107-018-1239-7[29] Yoichi Iwata and Takuto Shigemura. 2019. Separator-based pruned dynamic programming for Steiner tree. In Proceedings of the AAAI Conference on
Artificial Intelligence, Vol. 33. 1520–1527.
[30] Daniel Juhl, David M Warme, Pawel Winter, and Martin Zachariasen. 2018. The GeoSteiner software package for computing Steiner trees in theplane: an updated computational study. Mathematical Programming Computation 10, 4 (2018), 487–532. https://doi.org/10.1007/s12532-018-0135-8[31] Volker Kaibel and Andreas Loos. 2011. Finding Descriptions of Polytopes via Extended Formulations and Liftings. In Progress in Combinatorial
Optimization, A. Ridha Mahjoub (Ed.). Wiley.
[32] Rohit Kannan and James R Luedtke. 2021. A stochastic approximation method for approximating the efficient frontier of chance-constrained
nonlinear programs. Mathematical Programming Computation 13, 4 (2021), 705–751.
[33] R. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher (Eds.). Plenum Press,
85–103. https://doi.org/10.1007/978-1-4684-2001-2_9

936

Manuscript submitted to ACM

886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934

Enabling Research through the SCIP Optimization Suite 8.0
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986

19

[34] Thorsten Koch. 2004. Rapid Mathematical Prototyping. Dissertation. Technische Universität Berlin.
[35] Thorsten Koch, Alexander Martin, and Stefan Voß. 2001. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Springer US, Boston, MA,
285–325. https://doi.org/10.1007/978-1-4613-0255-1_9[36] Leo Liberti and James Ostrowski. 2014. Stabilizer-based symmetry breaking constraints for mathematical programs. Journal of Global Optimization
60 (2014), 183–194. https://doi.org/10.1007/s10898-013-0106-6[37] Jeffrey T Linderoth and Ted K Ralphs. 2005. Noncommercial software for mixed-integer linear programming. Integer programming: theory andpractice 3 (2005), 253–303.
[38] Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. 2016. PySCIPOpt: Mathematical
Programming in Python with the SCIP Optimization Suite. In Mathematical Software – ICMS 2016. Springer, 301–307. https://doi.org/10.1007/978-3319-42432-3_37[39] François Margot. 2002. Pruning by isomorphism in branch-and-cut. Mathematical Programming 94, 1 (2002), 71–90. https://doi.org/10.1007/s10107002-0358-2[40] François Margot. 2003. Exploiting orbits in symmetric ILP. Mathematical Programming 98, 1–3 (2003), 3–21. https://doi.org/10.1007/s10107-0030394-6[41] François Margot. 2010. Symmetry in Integer Linear Programming. In 50 Years of Integer Programming, Michael Jünger, Thomas M. Liebling, Denis
Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey (Eds.). Springer, 647–686.
https://doi.org/10.1007/978-3-540-68279-0_17[42] Sonja Mars. 2013. Mixed-Integer Semidefinite Programming with an Application to Truss Topology Design. Dissertation. FAU Erlangen-Nürnberg.
[43] Frederic Matter and Marc E. Pfetsch. 2021. Presolving for Mixed-Integer Semidefinite Optimization. Technical Report. Optimization Online.
http://www.optimization-online.org/DB_HTML/2021/10/8614.html[44] Lluís-Miquel Munguía, Geoffrey Oxberry, and Deepak Rajan. 2016. PIPS-SBB: A Parallel Distributed-Memory Branch-and-Bound Algorithm
for Stochastic Mixed-Integer Programs. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 730–739.
https://doi.org/10.1109/IPDPSW.2016.159[45] Lluís-Miquel Munguía, Geoffrey Oxberry, Deepak Rajan, and Yuji Shinano. 2019. Parallel PIPS-SBB: multi-level parallelism for stochastic mixedinteger programs. Computational Optimization and Applications 73, 2 (2019), 575–601. https://doi.org/10.1007/s10589-019-00074-0[46] James Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio. 2011. Orbital branching. Mathematical Programming 126, 1 (2011), 147–178.
https://doi.org/10.1007/s10107-009-0273-x[47] Tobias Polzin. 2003. Algorithms For the Steiner Problem in Networks. Dissertation. Saarland University.
[48] Antoine Prouvost, Justin Dumouchelle, Maxime Gasse, Didier Chételat, and Andrea Lodi. 2021. Ecole: A library for learning inside MILP solvers.
arXiv preprint arXiv:2104.02828 (2021).
[49] Daniel Rehfeldt. 2021. Faster Algorithms for Steiner Tree and Related Problems: From Theory to Practice. Dissertation. Technische Universität Berlin.
[50] Daniel Rehfeldt, Henriette Franz, and Thorsten Koch. 2020. Optimal Connected Subgraphs: Formulations and Algorithms. ZIB-Report 20-23. Zuse
Institute Berlin.
[51] Daniel Rehfeldt and Thorsten Koch. 2021. Implications, conflicts, and reductions for Steiner trees. Mathematical Programming (2021). https://doi.org/10.1007/s10107-021-01757-5 To appear.
[52] Daniel Rehfeldt and Thorsten Koch. 2021. On the Exact Solution of Prize-Collecting Steiner Tree Problems. INFORMS Journal on Computing (2021).
https://doi.org/10.1287/ijoc.2021.1087 To appear.
[53] D. M. Ryan and B. A. Foster. 1981. An integer programming approach to scheduling. In Computer Scheduling of Public Transport Urban Passenger
Vehicle and Crew Scheduling, A. Wren (Ed.). North Holland, Amsterdam, 269–280.
[54] Domenico Salvagnin. 2018. Symmetry Breaking Inequalities from the Schreier-Sims Table. In Integration of Constraint Programming, Artificial
Intelligence, and Operations Research, Willem-Jan van Hoeve (Ed.). Springer, 521–529. https://doi.org/10.1007/978-3-319-93031-2_37[55] Lars Schewe, Martin Schmidt, and Dieter Weninger. 2020. A Decomposition Heuristic for Mixed-Integer Supply chain Problems. Operations Research
Letters 48, 3 (2020), 225–232. https://doi.org/10.1016/j.orl.2020.02.006[56] H. D. Sherali and B. M. Fraticelli. 2002. Enhancing RLT relaxations via a new class of semidefinite cuts. Journal of Global Optimization 22 (2002),
233–261. https://doi.org/10.1023/A:1013819515732[57] Yuji Shinano. 2018. The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound. In Operations Research Proceedings
2017, Natalia Kliewer, Jan Fabian Ehmke, and Ralf Borndörfer (Eds.). Springer, 143–149. https://doi.org/10.1007/978-3-319-89920-6_20[58] Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, and Thorsten Koch. 2012. ParaSCIP: A Parallel Extension of SCIP. In Competence inHigh Performance Computing 2010, Christian Bischof, Heinz-Gerd Hegering, Wolfgang E. Nagel, and Gabriel Wittum (Eds.). Springer, 135–148.
https://doi.org/10.1007/978-3-642-24025-6_12[59] Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, and Michael Winkler. 2016. Solving Open MIP Instances withParaSCIP on Supercomputers Using up to 80,000 Cores. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 770–779.
https://doi.org/10.1109/IPDPS.2016.56[60] Yuji Shinano, Timo Berthold, and Stefan Heinz. 2018. ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on
supercomputers. Optimization Methods and Software 33, 3 (2018), 530–539. https://doi.org/10.1080/10556788.2018.1428602

987
988

Manuscript submitted to ACM

20
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012

[61] Yuji Shinano, Stefan Heinz, Stefan Vigerske, and Michael Winkler. 2018. FiberSCIP: A Shared Memory Parallelization of SCIP. INFORMS Journal on
Computing 30, 1 (2018), 11–30. https://doi.org/10.1287/ijoc.2017.0762[62] Yuji Shinano, Daniel Rehfeldt, and Tristan Gally. 2019. An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers:
A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-Libraries. In 2019 IEEE
International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 530–541. https://doi.org/10.1109/IPDPSW.2019.00095[63] Yuji Shinano, Daniel Rehfeldt, and Thorsten Koch. 2019. Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores. In
Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Louis-Martin Rousseau and Kostas Stergiou (Eds.). Springer,
Cham, 529–539.
[64] E.M.B. Smith and C.C. Pantelides. 1999. A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex
MINLPs. Computers & Chemical Engineering 23, 4-5 (1999), 457–478. https://doi.org/10.1016/s0098-1354(98)00286-5[65] Nariaki Tateiwa, Yuji Shinano, Satoshi Nakamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, and Katsuki Fujisawa. 2020. Massive Parallelization
for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework. In SC20: International Conference for High Performance Computing,
Networking, Storage and Analysis. 1–15. https://doi.org/10.1109/SC41405.2020.00064[66] Nariaki Tateiwa, Yuji Shinano, Keiichiro Yamamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, and Katsuki Fujisawa. 2021. CMAP-LAP:
Configurable Massively Parallel Solver for Lattice Problems. ZIB-Report 21-16. Zuse Institute Berlin.
[67] Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Keiichiro Yamamura, Shizuo Kaji, and Katsuki Fujisawa. 2021. Massively parallel sharing lattice basis
reduction. ZIB-Report 21-38. Zuse Institute Berlin.
[68] Siavash Vahdati Daneshmand. 2004. Algorithmic Approaches to the Steiner Problem in Networks. Dissertation. Universität Mannheim.
[69] F. Vanderbeck. 2011. Branching in Branch-and-Price: A Generic Scheme. Mathematical Programming 130, 2 (2011), 249–294. https://doi.org/10.
1007/s10107-009-0334-1[70] Stefan Vigerske and Ambros Gleixner. 2017. SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework.
Optimization Methods & Software 33, 3 (2017), 563–593. https://doi.org/10.1080/10556788.2017.1335312[71] D. Villeneuve, J. Desrosiers, M.E. Lübbecke, and F. Soumis. 2005. On Compact Formulations for Integer Programs Solved by Column Generation.
Annals of Operations Research 139, 1 (2005), 375–388. https://doi.org/10.1007/s10479-005-3455-9[72] Fabian Wegscheider. 2019. Exploiting Symmetry in Mixed-Integer Nonlinear Programming. Master’s thesis. Zuse Institute Berlin.
[73] Roland Wunderling. 1996. Paralleler und Objektorientierter Simplex-Algorithmus. Dissertation. Technische Universität Berlin.

1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040

Bestuzheva et al.

Manuscript submitted to ACM