SCIP Workshop 2018

Structure of the SCIP Introduction Day

9:30–11:00 Introduction to SCIP
11:00–11:30 Coffee Break
11:30–12:30 Installation of SCIP and GCG
12:30–14:00 Lunch
14:00–17:30 Programming Exercises
15:30–16:00 Coffee Break

Visit scip.zib.de/workshop2018 for all information.

Tomorrow and on Thursday: Scientific Talks

Plenary Talk Wednesday, 11:30

Ruth Misener, Imperial College London, UK

Gregor Hendel – SCIP Introduction 1/71

Introduction to SCIP

Gregor Hendel
SCIP Workshop 2018, Aachen, March 6, 2018
What is SCIP?

SCIP (Solving Constraint Integer Programs) . . .

• provides a full-scale MIP and MINLP solver,

• is constraint based,
• incorporates
• MIP features (cutting planes, LP relaxation), and
• MINLP features (spatial branch-and-bound, OBBT)
• CP features (domain propagation),
• SAT-solving features (conflict analysis, restarts),
• is a branch-cut-and-price framework,
• has a modular structure via plugins,
• is free for academic purposes,
• and is available in source-code under http://scip.zib.de !

Gregor Hendel – SCIP Introduction 2/71

Meet the SCIP Team

31 active developers
• 7 running Bachelor and Master projects
• 16 running PhD projects
• 8 postdocs and professors

4 development centers in Germany

• ZIB: SCIP, SoPlex, UG, ZIMPL
• TU Darmstadt: SCIP and SCIP-SDP
• FAU Erlangen-Nürnberg: SCIP
• RWTH Aachen: GCG

Many international contributors and users

• more than 10 000 downloads per year from 100+ countries

Careers
• 10 awards for Masters and PhD theses: MOS, EURO, GOR, DMV
• 7 former developers are now building commercial optimization software at
CPLEX, FICO Xpress, Gurobi, MOSEK, and GAMS

Gregor Hendel – SCIP Introduction 3/71

Outline

SCIP – Solving Constraint Integer Programs

Constraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suite

http://scip.zib.de

Gregor Hendel – SCIP Introduction 4/71

Outline

SCIP – Solving Constraint Integer Programs

Constraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suite

http://scip.zib.de

Gregor Hendel – SCIP Introduction 5/71

An example: the Traveling Salesman Problem

Definition (TSP)
Given a complete graph
G = (V , E ) and distances de for
all e ∈ E :
Find a Hamiltonian cycle (cycle
containing all nodes, tour) of
minimum length.

K8

Gregor Hendel – SCIP Introduction 6/71

An example: the Traveling Salesman Problem

Definition (TSP)
Given a complete graph
G = (V , E ) and distances de for
all e ∈ E :
Find a Hamiltonian cycle (cycle
containing all nodes, tour) of
minimum length.

K8

Gregor Hendel – SCIP Introduction 6/71

An example: the Traveling Salesman Problem

Definition (TSP)
Given a complete graph
G = (V , E ) and distances de for
all e ∈ E :
Find a Hamiltonian cycle (cycle
containing all nodes, tour) of
minimum length.

Gregor Hendel – SCIP Introduction 6/71

What is a Constraint Integer Program?

Mixed Integer Program Constraint Program

Objective function: Objective function:

. linear function . arbitrary function

Feasible set: Feasible set:

. described by linear constraints . given by arbitrary constraints

Variable domains: Variable domains:

. real or integer values . arbitrary (usually finite)

min cT x min c(x)

s.t. Ax ≤ b s.t. x ∈F
(xI , xC ) ∈ ZI × RC (xI , xN ) ∈ ZI × X

Gregor Hendel – SCIP Introduction 7/71

TSP – Integer Programming Formulation

Given
• complete graph G = (V , E ) xe

• distances de > 0 for all e ∈ E

Binary variables
• xe = 1 if edge e is used
K8

Gregor Hendel – SCIP Introduction 8/71

TSP – Integer Programming Formulation

Given
• complete graph G = (V , E ) xe

• distances de > 0 for all e ∈ E

Binary variables
• xe = 1 if edge e is used
K8

X
min de xe
e∈E
X
subject to xe = 2 ∀v ∈ V
e∈δ(v )
X
xe ≥ 2 ∀S ⊂ V , S 6= ∅
e∈δ(S)

xe ∈ {0, 1} ∀e ∈ E

Gregor Hendel – SCIP Introduction 8/71

TSP – Integer Programming Formulation

Given
• complete graph G = (V , E ) xe

• distances de > 0 for all e ∈ E

Binary variables
• xe = 1 if edge e is used
K8

X
min de xe
e∈E
X
subject to xe = 2 ∀v ∈ V node degree
e∈δ(v )
X
xe ≥ 2 ∀S ⊂ V , S 6= ∅
e∈δ(S)

xe ∈ {0, 1} ∀e ∈ E

Gregor Hendel – SCIP Introduction 8/71

TSP – Integer Programming Formulation

Given
• complete graph G = (V , E ) xe

• distances de > 0 for all e ∈ E

Binary variables
• xe = 1 if edge e is used
K8

X
min de xe
e∈E
X
subject to xe = 2 ∀v ∈ V
e∈δ(v )
X
xe ≥ 2 ∀S ⊂ V , S 6= ∅
e∈δ(S) subtour elimination
xe ∈ {0, 1} ∀e ∈ E

Gregor Hendel – SCIP Introduction 8/71

TSP – Integer Programming Formulation

Given
• complete graph G = (V , E ) xe

• distances de > 0 for all e ∈ E

Binary variables
• xe = 1 if edge e is used
K8

X
min de xe distance
e∈E
X
subject to xe = 2 ∀v ∈ V
e∈δ(v )
X
xe ≥ 2 ∀S ⊂ V , S 6= ∅
e∈δ(S)

xe ∈ {0, 1} ∀e ∈ E

Gregor Hendel – SCIP Introduction 8/71

TSP – Constraint Programming Formulation

Given
• complete graph G = (V , E )
• for each e ∈ E a distance de > 0 xv

Integer variables
• xv position of v ∈ V in tour
K8

Gregor Hendel – SCIP Introduction 9/71

TSP – Constraint Programming Formulation

8
Given 7 2
• complete graph G = (V , E )
• for each e ∈ E a distance de > 0 3 1

Integer variables
• xv position of v ∈ V in tour 4 6
5

min length(x1 , . . . , xn )
subject to alldifferent(x1 , . . . , xn )
xv ∈ {1, . . . , n} ∀v ∈ V

Gregor Hendel – SCIP Introduction 9/71

What is a Constraint Integer Program?

Constraint Integer Program

min cT x
Objective function:
s.t. x ∈F
. linear function (xI , xC ) ∈ ZI × RC
Feasible set: Remark:

. described by arbitrary constraints • arbitrary objective or variables

modeled by constraints
Variable domains:

. real or integer values

Gregor Hendel – SCIP Introduction 10/71

What is a Constraint Integer Program?

Constraint Integer Program min

X
de xe
e∈E
Objective function: s.t.
X
xe =2 ∀v ∈ V
e∈δ(v )
nosubtour(x)
. linear function
xe ∈ {0, 1} ∀e ∈ E

Feasible set: (CIP formulation of TSP)

. described by arbitrary constraints Single nosubtour constraint rules

out subtours (e.g. by domain prop-
Variable domains: agation). It may also separate sub-
tour elimination inequalities.
. real or integer values

Gregor Hendel – SCIP Introduction 10/71

Mixed-Integer Nonlinear Programs (MINLPs)

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

0
100
200
10 200 300

0 200

5
0

−200
−1 1

−1
1

convex or nonconvex

Gregor Hendel – SCIP Introduction 11/71

Application: Data Classification

Support Vector Machine, e.g., with ramp loss.

n
w Tw C X
min + (ξi + 2(1 − zi ))
2 n i=1

s.t. zi (yi (w T xi + b) − 1 + ξi ) ≥ 0 ∀i
ξi ∈ [0, 2], zi ∈ {0, 1} ∀i
d
w ∈R , b∈R

Gregor Hendel – SCIP Introduction 12/71

Constraint Integer Programming

• Mixed Integer Programs

MIP

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

• Mixed Integer Programs

• SATisfiability problems
MIP

SAT

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

• Mixed Integer Programs

• SATisfiability problems
MIP
• Pseudo-Boolean Optimization

SAT PBO

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

• Mixed Integer Programs

• SATisfiability problems
MIP
• Pseudo-Boolean Optimization
• Mixed Integer Nonlinear Programs SAT PBO MINLP

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

• Mixed Integer Programs

• SATisfiability problems
MIP
• Pseudo-Boolean Optimization
• Mixed Integer Nonlinear Programs SAT PBO MINLP CP
• Constraint Programming

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

CIP
• Mixed Integer Programs
• SATisfiability problems
MIP
• Pseudo-Boolean Optimization
• Mixed Integer Nonlinear Programs SAT PBO MINLP CP
• Constraint Programming
• Constraint Integer Programming

Gregor Hendel – SCIP Introduction 13/71

Constraint Integer Programming

CIP
• Mixed Integer Programs
• SATisfiability problems
MIP
• Pseudo-Boolean Optimization
• Mixed Integer Nonlinear Programs SAT PBO MINLP CP
• Constraint Programming
• Constraint Integer Programming

Relation to CP and MIP

• Every MIP is a CIP. “MIP ( CIP”

• Every CP over a finite domain space is a CIP. “FD ( CIP”

Gregor Hendel – SCIP Introduction 13/71

Outline

SCIP – Solving Constraint Integer Programs

Constraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suite

http://scip.zib.de

Gregor Hendel – SCIP Introduction 14/71

Branch-and-bound

Gregor Hendel – SCIP Introduction 15/71

SCIP Interactive Shell Basics

Basic Workflow
r e a d . . / c h e c k / i n s t a n c e s /MIP/ b e l l 5 . mps
optimize
write solution mysolution . sol
quit

Displaying information
Use the display ... command to enter the menu and

• obtain solution information

• print the current transproblem to the console
• display plugin information, e.g., list all available branching rules

Changing Settings
Use the set ... command to list the settings menu.

Gregor Hendel – SCIP Introduction 16/71

Important Parameters

Numerical parameters
These must be set before reading a problem.

• numerics/feastol, default 10−6

• numerics/epsilon, default 10−9
• numerics/infinity, default 1020

Limits

• limits/time
• limits/nodes
• limits/gap

Randomization

• randomization/randomseedshift
• randomization/lpseed
• randomization/permutationseed
Gregor Hendel – SCIP Introduction 17/71
Different Tasks – Different Plugins

Different plugin classes are responsible of the following tasks.

1. Presolving and node propagation
• Constraint handlers
• Presolvers
• Propagators
2. Separation
• Constraint handlers
• Separators
3. Improving solutions
• Primal heuristics
4. Branching
• Constraint handlers
• Branching rules
5. Node selection
• Node selectors

Gregor Hendel – SCIP Introduction 18/71

Operational Stages

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

Gregor Hendel – SCIP Introduction 19/71

Operational Stages

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

• Basic data structures are allocated and initialized.

• User includes required plugins (or just takes default plugins).

Gregor Hendel – SCIP Introduction 19/71

Problem Specification

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

• User creates and modifies the original problem instance.

• Problem creation is usually done in file readers.

Gregor Hendel – SCIP Introduction 20/71

Define Variables (LOP Example)

SCIP_VAR * var ;
SCIP_CALL ( // return value macro
SCIPcreateVar (
scip , // SCIP pointer
& var , // save in variable
" varname " , // pass variable name
0.0 , // lower bound
1.0 , // upper bound
length , // obj . value
SCIP_VARTYPE_BINARY , // type
TRUE , // initial
FALSE , // removable
NULL , NULL , NULL , // no callback functions
NULL // no variable data
)
);
SCIP_CALL ( SCIPaddVar ( scip , var ) ); // add var .

Gregor Hendel – SCIP Introduction 21/71

TSP: Define Degree Constraints

SCIP_CALL ( S C I P c r e a t e C o n s L i n e a r (
scip , // SCIP pointer
& cons , // save in cons
" consname " , // name
nvar , // number of variables
vars , // array of variables
vals , // array of values
2.0 , // left hand side
2.0 , // right hand side ( equation )
TRUE , // initial ?
FALSE , // separate ?
TRUE , // enforce ?
TRUE , // check ?
TRUE , // propagate ?
FALSE , // local ?
FALSE , // modifable ?
FALSE , // dynamic ?
FALSE , // removable ?
FALSE // stick at node ?
));
SCIP_CALL ( SCIPaddCons ( scip , cons ) ); // add constraint
SCIP_CALL ( SCIPreleaseCons ( scip , & cons ) ); // free cons . space

MIPs are specified using linear constraints only (may be “upgraded”).

Gregor Hendel – SCIP Introduction 22/71

Transformation

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

• Creates a working copy of the original problem.

Gregor Hendel – SCIP Introduction 23/71

Original and Transformed Problem

Original CIP Transformed CIP

Original variables Transformed variables

Original constraints Transformed constraints

• data is copied into separate memory area

• presolving and solving operate on transformed problem
• original data can only be modified in problem modification stage

Gregor Hendel – SCIP Introduction 24/71

Presolving

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

Gregor Hendel – SCIP Introduction 25/71

Presolving

Task

• reduce size of model by

removing irrelevant information
• strengthen LP relaxation by
exploiting integrality information
• make the LP relaxation
numerically more stable
• extract useful information

Primal Reductions: • based on feasibility reasoning

• no feasible solution is cut off

Dual Reductions: • consider objective function

• at least one optimal solution remains

Gregor Hendel – SCIP Introduction 26/71

Presolving Tips and Parameters

Use display presolvers to list all presolvers of SCIP.

Disable Presolving
Disable all presolving for a model

s e t p r e s o l v i n g emphasis o f f

Deactivate single techniques

s e t p r e s o l v i n g tworowbnd maxrounds 0
s e t propa gating probing maxprerounds 0
s e t c o n s t r a i n t s components a d v a n c e d m a x p r e r o u n d s 0

Aggressive Presolving
s e t p r e s o l v i n g emphasis a g g r e s s i v e

General Rule of Thumb

Only deactivate single presolving techniques if you encounter performance
problems.
Gregor Hendel – SCIP Introduction 27/71
Solving

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

Gregor Hendel – SCIP Introduction 28/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 29/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 29/71

Node Selection

Techniques

• basic rules
• depth first search (DFS)
→ early feasible solutions
• best bound search (BBS)
→ improve dual bound
• best estimate search (BES)
→ improve primal bound

Task
• combinations
• improve primal bound • BBS or BES with plunging
• keep comp. effort small • hybrid BES/BBS
• interleaved BES/BBS
• improve global dual bound

Gregor Hendel – SCIP Introduction 30/71

Node Selection Tips and Parameters

Available Node Selectors

display nodeselectors

node s e l e c t o r s t d p r i o r i t y memsave p r i o description

−−−−−−−−−−−−− −−−−−−−−−−−− −−−−−−−−−−−− −−−−−−−−−−−
estimate 200000 100 b e s t e s t i m a t e s e a r c h
bfs 100000 0 best f i r s t search
...
dfs 0 100000 d e p t h f i r s t s e a r c h

Switching Node Selectors

Only the node selector with highest standard priority is active. Use

s e t n o d e s e l e c t i o n d f s s t d p r i o r i t y 1000000

to activate depth first search also in non-memsave mode.

Gregor Hendel – SCIP Introduction 31/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 32/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 32/71

Domain Propagation

x1 x1

Techniques
x2 x2
• constraint specific
⇒
x3 x3 • each cons handler may provide a
propagation routine
• reduced presolving (usually)
x4 x4
• dual propagation
• root reduced cost strengthening
Task
• objective function
• simplify model locally
• special structures
• improve local dual bound • variable bounds
• detect infeasibility

Gregor Hendel – SCIP Introduction 33/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 34/71

LP Solving

• LP solver is a black box

• interface to different LP solvers:
SoPlex, CPLEX, XPress, Gurobi,
CLP, . . .
• primal/dual simplex
• barrier with/without crossover

• feasibility double-checked by SCIP

• condition number check
• resolution by changing parameters:
scaling, tolerances, solving from scratch, other simplex

Gregor Hendel – SCIP Introduction 35/71

LP Solving Tips and Parameters

Most Important LP Parameters

• lp/initalgorithm, lp/resolvealgorithm
• Primal/Dual Simplex Algorithm
• Barrier w and w/o crossover
• lp/pricing
• normally LP solver specific default
• Devex
• Steepest edge
• Quick start steepest edge
• lp/threads

Slow LP performance is a blocker for the solving process and can sometimes be
manually tuned significantly.

Gregor Hendel – SCIP Introduction 36/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 37/71

Pricing

Pricing

• find variable with negative reduced

costs
• or prove that there exists none
• typically problem specific

• dynamic aging of variables

Branch-and-Price
• problem variable pricer to add
• huge number of variables them again
• start with subset • early branching possible
• add others, when needed • lazy variable bounds

Gregor Hendel – SCIP Introduction 38/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 39/71

Cutting Plane Separation

Techniques

• general cuts
• complemented MIR cuts
• Gomory mixed integer cuts
• strong Chvátal-Gomory cuts
• implied bound cuts
• reduced cost strengthening

Task • problem specific cuts

• 0-1 knapsack problem
• strengthen relaxation • stable set problem
• 0-1 single node flow problem
• add valid constraints
• generate on demand

Gregor Hendel – SCIP Introduction 40/71

Cuts for the 0-1 Knapsack Problem

Feasible region: (b ∈ Z+ , aj ∈ Z+ ∀ j ∈ N)
X
X BK := { x ∈ {0, 1}n : aj xj ≤ b }
j∈N

Minimal Cover: C ⊆ N
•
P
aj > b 5x1 + 6x2 + 2x3 + 2x4 ≤ 8
j∈C
P
• j∈C \{i} aj ≤ b ∀i ∈ C
Minimal cover:
C = {2, 3, 4}
Minimal Cover Inequality Minimal cover inequality:
X x2 + x3 + x4 ≤ 2
xj ≤ |C | − 1
j∈C

Gregor Hendel – SCIP Introduction 41/71

Separation Tips and Parameters

Disable/Speed up/Emphasize All Separation

s e t s e p a r a t i n g emphasis o f f / f a s t / a g g r e s s i v e

Disable Single Separation Techniques

s e t s e p a r a t i n g c l i q u e f r e q −1
s e t c o n s t r a i n t s c a r d i n a l i t y s e p a f r e q −1

Some Important Parameters

• separating/maxcuts, separating/maxcutsroot
• separating/maxrounds, separating/maxroundsroot
• separating/maxstallrounds, separating/maxstallroundsroot

Gregor Hendel – SCIP Introduction 42/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 43/71

Constraint Enforcement

LP solution may violate a constraint not contained in the relaxation.

Enforcing is necessary for a correct implementation!

Constraint handler resolves the infeasibility by ...

• Reducing a variable’s domain,
• Separating a cutting plane (may use integrality),
• Adding a (local) constraint,
• Creating a branching,
• Concluding that the subproblem is infeasible and can be cut off, or
• Just saying “solution infeasible”.

Gregor Hendel – SCIP Introduction 44/71

Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Constraint Enforcement

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

• Reduced domain • Added cut • Cutoff • Infeasible

• Added constraint • Branched • Feasible
Gregor Hendel – SCIP Introduction 45/71
Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 46/71

Branching Rules

Techniques

• branching on variables
• most infeasible
• least infeasible
• random branching
• strong branching
• pseudocost
• reliability
• VSIDS
Task • hybrid reliability/inference

• divide into (disjoint) • branching on constraints

• SOS1
subproblems
• SOS2
• improve local bounds

Gregor Hendel – SCIP Introduction 47/71

Branching Rule Tips and Parameters

Branching Rule Selection

Branching rules are applied in decreasing order of priority.

SCIP> d i s p l a y b r a n c h i n g

branching r ule p r i o r i t y maxdepth m a x b d d i s t

−−−−−−−−−−−−−− −−−−−−−− −−−−−−−− −−−−−−−−−
relpscost 10000 −1 100.0%
pscost 2000 −1 100.0%
inference 1000 −1 100.0%
mostinf 100 −1 100.0%

Reliability Branching Parameters

All parameters prefixed with branching/relpscost/

• sbiterquot, sbiterofs to increase the budget for strong branching

• minreliable (= 1), maxreliable (= 5) to increase threshold to consider
pseudo costs as reliable
Gregor Hendel – SCIP Introduction 48/71
Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 49/71

Primal Heuristics

Techniques

• structure-based
• clique
• variable bounds
• rounding
• possibly solve final LP
• diving
• least infeasible
• guided
• objective diving
Task • objective feasibility pump
• improve primal bound • Large Neighborhood Search
• effective on average • RINS, local branching
• RENS
• guide remaining search • Adaptive LNS
• Completion of partial solutions

Gregor Hendel – SCIP Introduction 50/71

Primal Heuristics Tips and Parameters

Disable/Speed Up/Emphasize Heuristics

s e t h e u r i s t i c s emphasis o f f / f a s t / a g g r e s s i v e

Disable an individual heuristic via

s e t h e u r i s t i c s feaspump f r e q −1

Important Parameters

• heuristics/alns/nodesofs, heuristics/alns/nodesquot to increase

the computational budget of this LNS technique
• heuristics/guideddiving/... lpsolvefreq, maxlpiterofs
maxlpiterquot to control the LP solving during this diving technique

Advice
Use emphasis settings. Do not attempt to individually tune heuristics by hand.

Gregor Hendel – SCIP Introduction 51/71

Flow Chart SCIP

Presolving

Stop Domain propagation

Node selection Solve LP

Pricing
Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel – SCIP Introduction 52/71

Conflict Analysis

Techniques

• Analyze:
• Propagation conflicts
• Infeasible LPs
• Bound-exceeding LPs
• Strong branching conflicts
• Detection:
Task • Cut in conflict graph
• LP: Dual ray heuristic
• Analyze infeasibility
• Use conflicts:
• Derive valid constraints
• Only for propagation
• Help to prune other nodes • As cutting planes

Gregor Hendel – SCIP Introduction 53/71

Operational Stages

Init Init Solve

Problem Transforming Presolving Solving

Free Transform Free Solve

Gregor Hendel – SCIP Introduction 54/71

Outline

SCIP – Solving Constraint Integer Programs

Constraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suite

http://scip.zib.de

Gregor Hendel – SCIP Introduction 55/71

The SCIP C API

• C code and documentation

• more than 800 000 lines of C code, 20% documentation
• over 50 000 assertions and 5 000 debug messages
• HowTos: plugins types, debugging, automatic testing
• 10 examples illustrating the use of SCIP
• 5 problem specific SCIP applications to solve Coloring, Steiner Tree, or
Multiobjective problems.
• Interface and usability
• Cross-platform availability due to CMake
• user-friendly interactive shell
• C++ wrapper classes
• LP solvers: SoPlex, CPLEX, Gurobi, Xpress, CLP, MOSEK, QSopt
• NLP solvers: IPOPT, FilterSQP, WORHP
• over 2 300 parameters and 15 emphasis settings

Gregor Hendel – SCIP Introduction 56/71

Interfaces to SCIP

• interactive shell supports 10 different input formats

→ cip, cnf, flatzinc, rlp, lp, mps, opb, pip, wbo, zimpl
• C API/callable library
• C++ wrapper classes
• Python interface
• Java JNI interface
• AMPL
• GAMS
• Matlab (see also OPTI toolbox,
http://www.i2c2.aut.ac.nz/Wiki/OPTI/)

Gregor Hendel – SCIP Introduction 57/71

Getting help

If you should ever get stuck, you can . . .

1. type help in the interactive shell

2. read the documentation http://scip.zib.de/doc/html
→ FAQ, HowTos for each plugin type, debugging, automatic testing, . . .
3. active mailing list scip@zib.de (350+ members)
• search the mailing list archive (append site:listserv/pipermail/scip)
• register http://listserv.zib.de/mailman/listinfo/scip/ and post
4. search or post on Stack Overflow using the tag scip (more than 100
questions already answered)

Gregor Hendel – SCIP Introduction 58/71

Structure of SCIP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 59/71

Structure of SCIP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 59/71

Structure of SCIP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 59/71

Plugin based design

SCIP core

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Gregor Hendel – SCIP Introduction 60/71

Plugin based design

SCIP core

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Plugins

• external callback objects

• interact with the framework through a very detailed interface

Gregor Hendel – SCIP Introduction 60/71

Plugin based design

SCIP core

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Plugins

• external callback objects

• interact with the framework through a very detailed interface
• SCIP knows for each plugin type:
• the number of available plugins
• priority defining the calling order (usually)
• SCIP does not know any structure behind a plugin
⇒ plugins are black boxes for the SCIP core

Gregor Hendel – SCIP Introduction 60/71

Plugin based design

SCIP core

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Plugins

• external callback objects

• interact with the framework through a very detailed interface
• SCIP knows for each plugin type:
• the number of available plugins
• priority defining the calling order (usually)
• SCIP does not know any structure behind a plugin
⇒ plugins are black boxes for the SCIP core

⇒ Very flexible branch-and-bound based search algorithm

Gregor Hendel – SCIP Introduction 60/71

Types of Plugins

• Constraint handler: assures feasibility, strengthens formulation

• Separator: adds cuts, improves dual bound
• Pricer: allows dynamic generation of variables
• Heuristic: searches solutions, improves primal bound
• Branching rule: how to divide the problem?
• Node selection: which subproblem should be regarded next?
• Presolver: simplifies the problem in advance, strengthens structure
• Propagator: simplifies problem, improves dual bound locally
• Reader: reads problems from different formats
• Event handler: catches events (e.g., bound changes, new solutions)
• Display: allows modification of output
• ...

Gregor Hendel – SCIP Introduction 61/71

A closer look: branching rules
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 62/71

 default

A closer look: branching rules

Conflict simple
shifting
rounding

allfull
bound strong
disjunc. full
strong

count
sols infer
cumu
ence
lative
Branch

indi
cator leastinf

relps
integral cost
mostinf
knap
sack random pscost

g
linear

Gregor Hendel – SCIP Introduction 62/71

What does SCIP know about branching rules?

• SCIP knows the number of available branching rules

• each branching rule has a priority
• SCIP calls the branching rule in decreasing order of priority
• the interface defines the possible results of a call:
• branched
• reduced domains
• added constraints
• detected cutoff
• did not run

Gregor Hendel – SCIP Introduction 63/71

How does SCIP call a branching rule?

/* start timing */
SCIP clockStart ( branchrule - > branchclock , set );

/* call external method */

SCIP_CALL ( branchrule - > branchexeclp ( set - > scip , branchrule ,
allowaddcons , result ) );

/* stop timing */
SCIPclockStop ( branchrule - > branchclock , set );

/* evaluate result */
if ( * result != SCIP_CUTOFF
&& * result != SCIP_CONSADDED
&& * result != SCIP_REDUCEDDOM
&& * result != SCIP_SEPARATED
&& * result != SCIP_BRANCHED
&& * result != SCIP_DIDNOTRUN )
{
S C I P e r rorMessage (
" branching rule <%s > returned invalid result code <%d > from LP \
solution branching \ n " ,
branchrule - > name , * result );
return S C IP _ IN VA L ID R ES UL T ;
}

Gregor Hendel – SCIP Introduction 64/71

What can a plugin access?

Plugins are allowed to access all global (core) information

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Gregor Hendel – SCIP Introduction 65/71

What can a plugin access?

Plugins are allowed to access all global (core) information

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Ideally, plugins should not access data of other plugins!!!

Gregor Hendel – SCIP Introduction 65/71

What can a plugin access?

Plugins are allowed to access all global (core) information

• branching tree • solution pool • clique table

• variables • cut pool • implication graph
• conflict analysis • statistics • ...

Ideally, plugins should not access data of other plugins!!!

Branching Rules

• LP solution • variables • statistics

Gregor Hendel – SCIP Introduction 65/71

Constraint Handlers

Constraint handlers

• most powerful plugins in SCIP

• define the feasible region
• a single constraint may represent a whole set of inequalities

Functions

• check and enforce feasibility of solutions

• can add linear representation to LP relaxation
• constraint-specific presolving, domain propagation, separation

Result
• SCIP is constraint based
• Advantage: flexibility
• Disadvantage: limited global view

Gregor Hendel – SCIP Introduction 66/71

Default Plugins

mps opb implied

bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 67/71

Extending SCIP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary trivial
redcost
ccg zpl
zero strong
implics half cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
vbound over dins branching
restart
dfs
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

zi round oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
xprs bound disjunc. full
xor and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 68/71

Extending SCIP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary default
redcost
ccg default
strong
implics default cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator cross local mutation
default over dins branching

default
··· Relax coef subnlp
hybrid diving objpscost
estim actcons
diving
diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

default oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

allfull
bound strong
var
default bound disjunc. full
default and strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 68/71

Extending SCIP: TSP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary default
redcost
tsp default
strong
implics default cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator local mutation
default 2-Opt
dins branching

default
··· Relax coef subnlp
hybrid diving objpscost
estim farthest diving
insert

estimate
Node
selector
SCIP Primal
Heuristic
octane

default oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
sol shifting
rounding
found

allfull
bound strong
var
default bound disjunc. full
default subtour strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 68/71

Extending SCIP: Coloring
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing sos
intto csol
binary default
redcost
default coloring
col
strong
implics default cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
bound Impli feaspump diving
shift cations root guided
redcost diving int
fixand
infer shifting
Propa
gator local mutation
default 2-Opt
dins branching

default
··· Relax coef subnlp
hybrid diving objpscost
estim
init diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

default oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
shifting
rounding

Ryan&
var bound Foster
bound disjunc. strong
default store
default Ryan&
Graph
Foster

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 68/71

Extending SCIP: STP
mps opb implied
bounds intobj
ppm gomory
lp

flow mcf
rlp cover
fix
odd
Reader cycle
cmir Separator
cnf sol

rapid
clique learn
probing cip sos
intto
binary default
redcost
stp default
strong
implics default cg

dualfix Presolver
pseudo fracdiving intdiving
Tree Pricer
obj
linesearch
Impli feaspump diving
stp cations root guided
redcost diving int
fixand
infer shifting
Propa
gator local mutation
default local dins branching

default
··· Relax coef subnlp
hybrid diving objpscost
estim
TM diving

estimate
Node
selector
SCIP Primal
Heuristic
octane

default oneopt
dfs pscost
veclen
Display Variable diving diving

bfs

under twoopt rins rens

Dialog Event cover
default
trivial rounding
shift&
prop
rootsol
trysol
default diving
default
Cutpool Conflict simple
sol shifting
rounding
found

allfull
bound strong
var
default bound disjunc. full
default stp
strong

count
spx sos2 sols infer
cumu
sos1 ence
lative
LP Branch

qso Constraint indi

soc leastinf
Handler cator

relps
none clp setppc integral cost
mostinf
quadr knap
msk cpx atic sack random pscost

or linking
orbi
linear
tope

logicor

Gregor Hendel – SCIP Introduction 68/71

Outline

SCIP – Solving Constraint Integer Programs

Constraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suite

http://scip.zib.de

Gregor Hendel – SCIP Introduction 69/71

SCIP Optimization Suite

• Toolbox for generating and solving constraint integer programs

• free for academic use, available in source code

Gregor Hendel – SCIP Introduction 70/71

SCIP Optimization Suite

• Toolbox for generating and solving constraint integer programs

• free for academic use, available in source code
ZIMPL
• model and generate LPs, MIPs, and MINLPs
SCIP
• MIP, MINLP and CIP solver, branch-cut-and-price framework
SoPlex
• revised primal and dual simplex algorithm
GCG
• generic branch-cut-and-price solver
UG
• framework for parallelization of MIP and MINLP solvers

Gregor Hendel – SCIP Introduction 70/71

Wrap-up

How to solve your MINLP optimization problem:

• write down the mathematical description

• modeling language, e.g., ZIMPL, generates input for MINLP solver
• SCIP can even read ZIMPL files directly

MIP and MINLP solving

• . . . is a bag of tricks
• new tricks are introduced almost every day
• advantages of SCIP
• open source, you can see everything that happens
• hundreds of parameters to play with
• broad scope
• easily extendable

Gregor Hendel – SCIP Introduction 71/71