Global Optimization of Mixed-Integer Nonlinear Programs with
SCIP 8

Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller,
Felipe Serrano, Stefan Vigerske, Fabian Wegscheider
Kyushu University
January, 20th, 2023
GAMS Software GmbH and Zuse Institute Berlin

TOC

Introduction
SCIP 7 (and before)
SCIP 8: updated framework
MINLP features in SCIP
BenchmarkIntroduction

What is SCIP?

SCIP (Solving Constraint Integer Programs) . . .
• provides a full-scale MIP and MINLP solver,• incorporates• MIP features (cutting planes, LP relaxation), and• MINLP features (spatial branch-and-bound, NLP relaxation)• CP features (domain propagation),• SAT-solving features (conflict analysis, restarts),• is a branch-cut-and-price framework,• has a modular structure via plugins,• is open-source (since November 2022),• and is available under https://www.scipopt.org.

Mixed-Integer Nonlinear Programming

min c T x
s.t. gk (x) ≤ 0
xi ∈ Z∀k ∈ [m]∀i ∈ I ⊆ [n]xi ∈ [ℓi , ui ]∀i ∈ [n]The functions gk : [ℓ, u] → R can be
0
200

10

100

200

5

0

or

−200

−1
−1

300
200

0

1
1

convexand are given in algebraic form.

nonconvex

Expression Trees

The algebraic structure of nonlinear constraints
is stored in a directed acyclic graph:log(x)2 + 2 log(x)y + y 2 ∈ [−∞, 4]x, y ∈ [1, 4]• nodes: variables, operations[−∞, 4]• arcs: flow of computation

+
2

·

2

log

×

·2

y
[1, 4]

x[1, 4]

Spatial Branch and Bound
SCIP solves MINLPs by spatial Branch & Bound.
LP relaxation via convexification and linearization:
convex functions

concave functionsxk(k ∈ 2Z + 1)

x ·y

Spatial Branch and Bound
SCIP solves MINLPs by spatial Branch & Bound.
LP relaxation via convexification and linearization:
convex functions

concave functions

xk

x ·y

(k ∈ 2Z + 1)

Branching on variables in violated nonconvex constraints:
1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

-1.0

-0.5

0.2

0.5

1.0

-1.0

-0.5

0.5

1.0

Spatial Branch and Bound
SCIP solves MINLPs by spatial Branch & Bound.
LP relaxation via convexification and linearization:
convex functions

concave functions

xk

x ·y

(k ∈ 2Z + 1)

Branching on variables in violated nonconvex constraints:
1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

-1.0

-0.5

0.2

0.5

1.0

-1.0

-0.5

0.5

. . . and bound tightening (FBBT, OBBT), primal heuristics (e.g.,
sub-NLP/MIP/MINLP), other special techniques

1.0

SCIP 7 (and before)

Reformulation in Presolve

Goal: Reformulate constraints such that only elementary cases (convex, concave, odd
power, quadratic) remain by introducing new variables and new constraints.
Considermin zs.t. exp(ln(1000) + 1 + x y ) ≤ z
x2 + y2 ≤ 2

Reformulation in Presolve

Goal: Reformulate constraints such that only elementary cases (convex, concave, odd
power, quadratic) remain by introducing new variables and new constraints.
Considermin zs.t. exp(ln(1000) + 1 + x y ) ≤ z
x2 + y2 ≤ 2

Reformulation takes apart exp(ln(1000) + 1 + x y ), thus SCIP actually solves theextended formulation
min z
s.t. exp(w ) ≤ zln(1000) + 1 + x y = w
x2 + y2 ≤ 2

Issue with explicit reformulation
SCIP solves reformulated problem fine:
SCIP Status: problem is solved [optimal solution found]
Solving Time (sec) : 0.08
Solving Nodes: 5
Primal Bound: +9.99999656552062e+02 (3 solutions)
Dual Bound: +9.99999656552062e+02
Gap: 0.00 %Issue with explicit reformulation
SCIP solves reformulated problem fine:
SCIP Status: problem is solved [optimal solution found]
Solving Time (sec) : 0.08
Solving Nodes: 5
Primal Bound: +9.99999656552062e+02 (3 solutions)
Dual Bound: +9.99999656552062e+02
Gap: 0.00 %Solution (x, y , z, w ) = (−1.000574549, 0.999425451, 999.999656552, 6.907754936) looks ok:
min zs.t. exp(w ) ≤ z

Violation
0.4659 · 10−6 ≤ feastol ✓ln(1000) + 1 + x y = w

0.6731 · 10−6 ≤ feastol ✓x2 + y2 ≤ 20.6602 · 10−6 ≤ feastol ✓Issue with explicit reformulation
SCIP solves reformulated problem fine:
SCIP Status: problem is solved [optimal solution found]
Solving Time (sec) : 0.08
Solving Nodes: 5
Primal Bound: +9.99999656552062e+02 (3 solutions)
Dual Bound: +9.99999656552062e+02
Gap: 0.00 %Solution (x, y , z, w ) = (−1.000574549, 0.999425451, 999.999656552, 6.907754936) looks ok:
min zs.t. exp(w ) ≤ z

Violation
0.4659 · 10−6 ≤ feastol ✓ln(1000) + 1 + x y = w

0.6731 · 10−6 ≤ feastol ✓x2 + y2 ≤ 20.6602 · 10−6 ≤ feastol ✓However, original exp(ln(1000) + 1 + x y ) ≤ z has too large violation:[nonlinear] <e1>: exp((7.9077552789821368151 +1 (<x> * <y>)))-1<z>[C]violation: right hand side is violated by 0.000673453314561812
best solution is not feasible in original problem<= 0;Problem with classic approach⇒ Explicit reformulation of constraints ...
• ... loses the connection to the original problem.
• ... loses distinction between original and auxiliary variables.
Thus, we may branch on auxiliary variables.
• ... prevents simultaneous exploitation of overlapping structures.

SCIP 8: updated framework

Main Ideas

Avoid explicit split-up of constraints.
• introduce extended formulation as annotation to the original formulation• use extended formulation for relaxation• use original formulation for feasibility checking• to resolve infeasibility in original constraints, tighten relaxation of extended
formulation

Main Ideas

Avoid explicit split-up of constraints.
• introduce extended formulation as annotation to the original formulation• use extended formulation for relaxation• use original formulation for feasibility checking• to resolve infeasibility in original constraints, tighten relaxation of extended
formulation
Everything nonlinear is an expression.
• represent all nonlinear constraints in one expression graph (DAG)• all algorithms (check, separation, propagation, etc.) work on the same expression
graph, no more specialized nonlinear constraints

Main Ideas

Avoid explicit split-up of constraints.
• introduce extended formulation as annotation to the original formulation• use extended formulation for relaxation• use original formulation for feasibility checking• to resolve infeasibility in original constraints, tighten relaxation of extended
formulation
Everything nonlinear is an expression.
• represent all nonlinear constraints in one expression graph (DAG)• all algorithms (check, separation, propagation, etc.) work on the same expression
graph, no more specialized nonlinear constraints• separate expression operators (+, ×) and high-level structures (quadratic,
semi-continuous, second order cone, etc.)

Expression Handlers

Each operator type (+, ×, pow, etc.) is implemented by an expression handler, which
can provide a number of callbacks:• evaluate and differentiate expression w.r.t. operands• interval evaluation and tighten bounds on operands• provide linear under- and over-estimators• inform about curvature, monotonicity, integrality• simplify, compare, print, parse, hash, copy, etc.
Expression handlers are like other SCIP plugins.
New ones can be added by users (YOU!).
Available handler: abs, cos, entropy, exp, log, pow, product, signpow, sin, sum, value,varExample: Extended Formulation (exprhdlr only)

Constraint:
log(x)2 + 2 log(x)y + y 2 ≤ 4This formulation is used to check feasibility and presolve.

+
2

·2

log

x

×

·2

y

Example: Extended Formulation (exprhdlr only)

Constraint:
log(x)2 + 2 log(x)y + y 2 ≤ 4This formulation is used to check feasibility and presolve.
Extended Formulation:

w1+

w1 ≤ 42log(x)2 + 2 log(x)y + y 2 = w1
·2

log

x

×

·2

y

Example: Extended Formulation (exprhdlr only)

Constraint:
log(x)2 + 2 log(x)y + y 2 ≤ 4This formulation is used to check feasibility and presolve.
Extended Formulation:

w1+

w1 ≤ 4
w2 + 2w3 + w4 = w1
2

log(x) = w2

w2

w3
·2

2

×

w4
·2

log(x)y = w3
y 2 = w4

log

x

y

Example: Extended Formulation (exprhdlr only)

Constraint:
log(x)2 + 2 log(x)y + y 2 ≤ 4This formulation is used to check feasibility and presolve.
Extended Formulation:

w1+

w1 ≤ 4
w2 + 2w3 + w4 = w1

w2
·2

w52 = w2
w5 y = w3
2

y = w4

w3

×

w4
·2

w5
log

log(x) = w5
Used to construct LP relaxation.

2

x

y

Nonlinearity Handlers

But log(x)2 + 2 log(x)y + y 2 ≤ 4 is convex and quadratic in (log(x), y ).

Nonlinearity Handlers

But log(x)2 + 2 log(x)y + y 2 ≤ 4 is convex and quadratic in (log(x), y ).
To explore structure, we now have Nonlinearity Handler:• Adds additional separation and/or propagation algorithms for structures thatcan be identified in the expression graph.
• Attached to nodes in expression graph, but does not define expressions nor
constraints.
• Examples: quadratics, convex and concave, second order cone, . . .
• Several nlhdlrs can be attached to a node in the expression graph.

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4

+
2

·

2

log

x

×

·2

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4

w1 ≤ 4

1. Annotate root with auxiliary variable w1 .

w1
+
2

·

2

log

x

×

·2

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4

w1 ≤ 4

1. Annotate root with auxiliary variable w1 .
2. Run detect of all nlhdlrs on + node.
w1
+
2

·

2

log

x

×

·2

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4
1. Annotate root with auxiliary variable w1 .
2. Run detect of all nlhdlrs on + node.

w1 ≤ 4
w22 + 2w2 y + y 2 ≤ w1

• nlhdlr convex• detects a convex quadratic structure,• signals that it can compute underestimators,• but requests an auxiliary variable w2 for log node.

w1
sepa:convex +
2

·

2

×

·2

w2
log

x

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4
1. Annotate root with auxiliary variable w1 .
2. Run detect of all nlhdlrs on + node.

w1 ≤ 4
w22 + 2w2 y + y 2 ≤ w1

• nlhdlr convex• detects a convex quadratic structure,• signals that it can compute underestimators,• but requests an auxiliary variable w2 for log node.

w1
sepa:convex +prop:quad.

• nlhdlr quadratic• also detects a quadratic structure,• signals that it can do domain propagation, and• notifies that it will use bounds of nodes log and y .

2

·

2

×

·2

w2
log

x

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4
1. Annotate root with auxiliary variable w1 .
2. Run detect of all nlhdlrs on + node.

w1 ≤ 4
w22 + 2w2 y + y 2 ≤ w1

• nlhdlr convex• detects a convex quadratic structure,• signals that it can compute underestimators,• but requests an auxiliary variable w2 for log node.

w1
sepa:convex +prop:quad.

• nlhdlr quadratic• also detects a quadratic structure,• signals that it can do domain propagation, and• notifies that it will use bounds of nodes log and y .

3. Run detect of all nlhdlrs on log node.

2

·

2

×

·2

w2
log

x

y

Example: Extended Formulation (with nlhdlrs)

Constraint: log(x)2 + 2 log(x)y + y 2 ≤ 4
1. Annotate root with auxiliary variable w1 .
2. Run detect of all nlhdlrs on + node.

w1 ≤ 4
w22 + 2w2 y + y 2 ≤ w1
log(x) = w2

• nlhdlr convex• detects a convex quadratic structure,• signals that it can compute underestimators,• but requests an auxiliary variable w2 for log node.

w1
sepa:convex +prop:quad.

• nlhdlr quadratic• also detects a quadratic structure,• signals that it can do domain propagation, and• notifies that it will use bounds of nodes log and y .

3. Run detect of all nlhdlrs on log node.
• No specialized nlhdlr signals success.
The expression handler will be used for bothunder/overestimation and propagation.

2

·

2

×

·2

w2
y

log

expr logxMINLP features in SCIP (teasers only)
SCIP features particular for nonlinear structures+ = new or improved in SCIP 8

Presolve• simplify expressions+ identify common subexpressions

Presolve• simplify expressions+ identify common subexpressions+ linearize products of binary variables

Presolve• simplify expressions+ identify common subexpressions+ linearize products of binary variables• try to restrict variables appearing in one constraint only to its bounds,
e.g., xy + yz ≤ u → y ∈ {ℓy , uy }[Hansen et.al., 1993]

Presolve• simplify expressions+ identify common subexpressions+ linearize products of binary variables• try to restrict variables appearing in one constraint only to its bounds,
e.g., xy + yz ≤ u → y ∈ {ℓy , uy }[Hansen et.al., 1993]• if QP, add KKT as redundant constraints

Presolve• simplify expressions+ identify common subexpressions+ linearize products of binary variables• try to restrict variables appearing in one constraint only to its bounds,
e.g., xy + yz ≤ u → y ∈ {ℓy , uy }[Hansen et.al., 1993]• if QP, add KKT as redundant constraints+ symmetry detection using expression graph[Liberti 2010, Wegscheider 2019]

Quadratics
Nonlinear handler for quadratic subexpressions:• provides domain propagation (variable bound tightening)+ intersection cuts for nonconvex quadratics[Chmiela, Muñoz, Serrano 2021]

1.0

S
0.5

C
(y,̂ w)̂

0.0

K
-0.5

-1.0
-1.0

-0.5

0.0

0.5

1.0

+ also as separator for implied quadratics det(2 × 2 minors of X ) = 0, X = xx T

Quadratics
Nonlinear handler for quadratic subexpressions:• provides domain propagation (variable bound tightening)+ intersection cuts for nonconvex quadratics[Chmiela, Muñoz, Serrano 2021]

1.0

S
0.5

C
(y,̂ w)̂

0.0

K
-0.5

-1.0
-1.0

-0.5

0.0

0.5

1.0

+ also as separator for implied quadratics det(2 × 2 minors of X ) = 0, X = xx T
Separator for implied PSD constraint (X ⪰ xx T ):+ SDP-cuts for 2 × 2 principal minors of X − xx T ⪰ 0

Quadratics
Nonlinear handler for quadratic subexpressions:• provides domain propagation (variable bound tightening)+ intersection cuts for nonconvex quadratics[Chmiela, Muñoz, Serrano 2021]

1.0

S
0.5

C
(y,̂ w)̂

0.0

K
-0.5

-1.0
-1.0

-0.5

0.0

0.5

1.0

+ also as separator for implied quadratics det(2 × 2 minors of X ) = 0, X = xx T
Separator for implied PSD constraint (X ⪰ xx T ):+ SDP-cuts for 2 × 2 principal minors of X − xx T ⪰ 0
Separator for edge-concave quadratics:• aggregate quadratic constraints to be edge-concave• separate facets from vertex-polyhedral convex hull

[Misener, Floudas 2012]

Bilinear
Nonlinear handler for bilinear expressions:• convexify and domain propagation for xy w.r.t. additional inequalities on x, y ,e.g., x ≤ y• inequalities found by 2D-projection of LP relaxation (≈ OBBT)[Linderoth 2004, Hijazi 2015, Locatelli 2016, Müller, Serrano, Gleixner 2020]

Bilinear
Nonlinear handler for bilinear expressions:• convexify and domain propagation for xy w.r.t. additional inequalities on x, y ,e.g., x ≤ y• inequalities found by 2D-projection of LP relaxation (≈ OBBT)[Linderoth 2004, Hijazi 2015, Locatelli 2016, Müller, Serrano, Gleixner 2020]

Reformulation Linearization Technique for bilinear products:+ cuts from multiplication of LP rows and bounds+ also for implicit products in mixed-binary linear problems[Adams, Sherali 1986, Achterberg, Bestuzheva, Gleixner 2022]

Second-Order Cones

Nonlinear handler for Second-Order Cones:+ detect SOC constraints from quadratics and some
Euclidean norms

Second-Order Cones

Nonlinear handler for Second-Order Cones:+ detect SOC constraints from quadratics and some
Euclidean norms• separate using disaggregated formulation[Vielma, et.al. 2016]⇓

Convexity and Concavity

Nonlinear handler for convex and concave expressions:+ find convex/concave subexpressions using composition
rules• gradient cuts on convex functions• facets of convex hull on concave function+ prefer extended formulations for convex case[Tawarmalani Sahinidis, 2005]

Convexity and Concavity

Nonlinear handler for convex and concave expressions:+ find convex/concave subexpressions using composition
rules• gradient cuts on convex functions• facets of convex hull on concave function+ prefer extended formulations for convex case[Tawarmalani Sahinidis, 2005]

Separator for supporting hyperplanes:• separators to linearize at boundary of convex NLP
relaxation• projection of given point, or linesearch to interior point[Veinott 1967, Kronqvist, Lundell, Westerlund 2016, Serrano, Schwarz, Gleixner 2020]

Perspective Strengthening

Nonlinear handler for perspective strengthening:+ detect expressions in semi-continuous variables (ℓx y ≤ x ≤ ux y , y ∈ {0, 1})+ strengthen under/overestimators for such expressions, e.g.,f (x̂) + ∇f (x̂)(x − x̂) ≤ w⇒

f (x̂)y + ∇f (x̂)(x − x̂y ) ≤ w[Frangioni, Gentile 2006, Bestuzheva, Gleixner, Vigerske 2021]

Quotients

Nonlinear handler for quotients:• to avoid ambiguity, there is no expression type for quotientsax+b
in nonlinear handler+ detect cy+d+ provide bound tightening+ provide linear under/overestimates[Zamora, Grossmann 1998]

Primal Heuristics• fix all integer vars, solve NLP to local optimalitymin• multistart with constraint consensus for NLPs

[Smith, Chinneck, Aitken 2013]• NLP-diving• solve sequence of regularized NLP reformulations of MINLP (“MPEC”)• fix nonlinear vars, solve remaining sub-MIP[Berthold, Gleixner 2014]• other large neighborhood search heuristics, solving sub-MINLPs[Berthold, Heinz, Pfetsch, Vigerske 2011]

NLP solving via Ipopt and CppAD

Domain Propagation (Variable Bound Tightening)• Feasibility-Based Bound Tightening (FBBT): as in constraint programming
1.0

0.5

0.0

-0.5

-1.0
-1.0

-0.5

0.0

0.5

1.0

• Optimization-Based Bound Tightening (OBBT): optimize variable over LP[Gleixner, Berthold, Müller, Weltge 2017]• OBBT over NLP relaxation

Interfaces
Readers for MINLP included:• MPS, LP, PIP, AMPL NL, OSiL, ZIMPLInterfaces:• C, Java• Python• Julia, Matlab• AMPL, GAMS
• ...

Benchmark

Solvers

Global MINLP solvers included in GAMS 41.2.0 (November 2022) and still maintained:• BARON 22.9.30: commercial solver by The Optimization Firm (Nick Sahinidis)
chooses between several LP/MIP/NLP subsolvers (CONOPT, CPLEX, . . . )• Lindo API 14.0.5099.162: commercial solver by Lindo Systems, Inc.
uses CONOPT and MOSEK as subsolvers• Octeract 4.5.1: commercial solver by Octeract, Ltd.
uses CPLEX as LP/MIP/QP/QCP solver, Ipopt as NLP solver• SCIP 8.0.2: open-source academic solver
uses CPLEX as LP solver, Ipopt (with MA27) as NLP solver

Benchmark Setting
Test set:• selected 200 instances from MINLPLib:• all solvers can handle (no sine, cosine, signpower)• solvable by at least one solver, but not trivial for all• varying degree of integrality• varying degree of nonlinearity• avoid too many instances with similar name

• 4 additional permutations of variables/equations ⇒ 1000 instances

Benchmark Setting
Test set:• selected 200 instances from MINLPLib:• all solvers can handle (no sine, cosine, signpower)• solvable by at least one solver, but not trivial for all• varying degree of integrality• varying degree of nonlinearity• avoid too many instances with similar name

• 4 additional permutations of variables/equations ⇒ 1000 instances
Settings:• relative gap tolerance 10−4 , absolute gap tolerance 10−6
• feasibility tolerance 10−6
• bound unbounded variables by 1012
• 2 hours time limit• 1 thread/process• 50 GB RAM

Why “bound unbounded variables by 1012 ” ???
• convex underestimators typicallyrequire variable bounds• without bounds, the relaxation may be
weak or even unboundedWhy “bound unbounded variables by 1012 ” ???
• convex underestimators typicallyrequire variable bounds• without bounds, the relaxation may be
weak or even unbounded
Solvers handle unbounded variables in different ways by default:• SCIP skips relaxations and hopes that branching will help ⇒ may not terminate• BARON sets missing bounds of vars in nonconvex terms to ≈ ±1010 ;does not claim global optimality anymore• Lindo API reduces bounds of all vars in nonconvex terms to ±1010 ;may still claim optimality• Octeract sets missing bounds of all variables to ±107 (!);
may still claim optimality

Why “bound unbounded variables by 1012 ” ???
• convex underestimators typicallyrequire variable bounds• without bounds, the relaxation may be
weak or even unbounded
Solvers handle unbounded variables in different ways by default:• SCIP skips relaxations and hopes that branching will help ⇒ may not terminate• BARON sets missing bounds of vars in nonconvex terms to ≈ ±1010 ;does not claim global optimality anymore• Lindo API reduces bounds of all vars in nonconvex terms to ±1010 ;may still claim optimality• Octeract sets missing bounds of all variables to ±107 (!);
may still claim optimality⇒ Default settings may mean that each solver solves a different subproblem of
the actual problem and may report a lower bound of the subproblem only.
Via parameters, we can enforce a more similar treatment of unbounded variables.

Results (Serial Mode)solvedtimeout

failmean time∗

BARON
Lindo API
Octeract
SCIP

790
538
671
776

183
323
279
183

27
139
50
41

75s
489s
184s
85s

virt. worst
virt. best

368
967

405
33

227
0

1505s
20s

# instances solved

1,000
BARON
Lindo API
Octeract
SCIP

800
600
400
200
0
100

101

102

103

time factor to best (τ )∗fails are accounted with timelimit

104

Feedback(Some of) the competition agrees with this benchmark... :-)https://twitter.com/TheOptFirm/status/1616127754033938463

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)• BARON can utilize parallelization in the MIP solver, when solving MIP relaxations

Considering only the selected 200 instances without permutations:

1 threadsolved time
BARON

161

64s

4 threads
solved time
160

58s

8 threads
solved time
160

57s

16 threads
solved time
158

59s

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)• BARON can utilize parallelization in the MIP solver, when solving MIP relaxations• Lindo API log says it uses parallellization (parallel tree search?)

Considering only the selected 200 instances without permutations:

1 threadsolved time
BARON
Lindo API

161
114

64s
424s

4 threads
solved time
160
114

58s
379s

8 threads
solved time
160
106

57s
460s

16 threads
solved time
158
107

59s
456s

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)• BARON can utilize parallelization in the MIP solver, when solving MIP relaxations• Lindo API log says it uses parallellization (parallel tree search?)• Octeract has been designed for parallel tree search from the beginning

Considering only the selected 200 instances without permutations:

1 threadsolved time
BARON
Lindo API
Octeract

161
114
134

64s
424s
179s

4 threads
solved time
160
114
133

58s
379s
147s

8 threads
solved time
160
106
138

57s
460s
118s

16 threads
solved time
158
107
135

59s
456s
123s

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)• BARON can utilize parallelization in the MIP solver, when solving MIP relaxations• Lindo API log says it uses parallellization (parallel tree search?)• Octeract has been designed for parallel tree search from the beginning• SCIP itself uses almost no parallelization when solving MINLPs,
but FiberSCIP is available (racing ramp-up, parallel tree search)Considering only the selected 200 instances without permutations:

1 threadsolved time
BARON
Lindo API
Octeract(Fiber)SCIP

161
114
134
161

64s
424s
179s
77s

4 threads
solved time
160
114
133
145

58s
379s
147s
94s

8 threads
solved time
160
106
138
147

57s
460s
118s
78s

16 threads
solved time
158
107
135
152

59s
456s
123s
75s

Parallel Mode
Limiting solvers to one CPU core is so 20th century....
Can these solvers utilize several cores? (assuming shared memory)• BARON can utilize parallelization in the MIP solver, when solving MIP relaxations• Lindo API log says it uses parallellization (parallel tree search?)• Octeract has been designed for parallel tree search from the beginning• SCIP itself uses almost no parallelization when solving MINLPs,
but FiberSCIP is available (racing ramp-up, parallel tree search)Considering only the selected 200 instances without permutations:

1 threadsolved time
BARON
Lindo API
Octeract(Fiber)SCIP

161
114
134
161

64s
424s
179s
77s

4 threads
solved time
160
114
133
145

58s
379s
147s
94s

8 threads
solved time
160
106
138
147

57s
460s
118s
78s

16 threads
solved time
158
107
135
152

59s
456s
123s
75s

The test set may include too many easy instances where parallelization cannot shine.

End!

For more details, see also
• the report Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8(K. Bestuzheva, A. Chmiela, B. Müller, F. Serrano, S. Vigerske, and F. Wegscheider),https://arxiv.org/abs/2301.00587, and• the release report of SCIP 8, https://arxiv.org/abs/2112.08872