Introduction to SCIP

Gregor Hendel, hendel@zib.de
SCIP Introduction Day
September 26, 2018
3rd IMI-ISM-ZIB MODAL Workshop

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, hendel@zib.de – SCIP Introduction

1/70

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-Nü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, hendel@zib.de – SCIP Introduction

2/70

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, hendel@zib.de – SCIP Introduction

3/70

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, hendel@zib.de – SCIP Introduction

4/70

An example: the Traveling Salesman Problem

Definition (TSP)
Given a complete graph
G = (V , E ) and distances de forall e ∈ E :Find a Hamiltonian cycle (cycle
containing all nodes, tour) of
minimum length.
K8Gregor Hendel, hendel@zib.de – SCIP Introduction

5/70

An example: the Traveling Salesman Problem

Definition (TSP)
Given a complete graph
G = (V , E ) and distances de forall e ∈ E :Find a Hamiltonian cycle (cycle
containing all nodes, tour) of
minimum length.
K8Gregor Hendel, hendel@zib.de – SCIP Introduction

5/70

An example: the Traveling Salesman Problem

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

Gregor Hendel, hendel@zib.de – SCIP Introduction

5/70

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
s.t.

cT x

min

Ax ≤ b(xI , xC ) ∈ZI × RC

Gregor Hendel, hendel@zib.de – SCIP Introduction

s.t.

c(x)
x ∈F
(xI , xN ) ∈ZI × X
6/70

TSP – Integer Programming Formulation
Given
xe

• complete graph G = (V , E )• distances de > 0 for all e ∈ E
Binary variables• xe = 1 if edge e is used

Gregor Hendel, hendel@zib.de – SCIP Introduction

K8

7/70

TSP – Integer Programming Formulation
Given
xe

• complete graph G = (V , E )• distances de > 0 for all e ∈ E
Binary variables• xe = 1 if edge e is used

min

X

K8
de xe

e∈E

subject toX

xe = 2∀v ∈ Vxe ≥ 2∀S ⊂ V , S 6= ∅e∈δ(v )Xe∈δ(S)xe ∈ {0, 1}

Gregor Hendel, hendel@zib.de – SCIP Introduction∀e ∈ E

7/70

TSP – Integer Programming Formulation
Given
xe

• complete graph G = (V , E )• distances de > 0 for all e ∈ E
Binary variables• xe = 1 if edge e is used

min

X

K8
de xe

e∈E

subject toXnode degree

xe = 2∀v ∈ Vxe ≥ 2∀S ⊂ V , S 6= ∅e∈δ(v )Xe∈δ(S)xe ∈ {0, 1}

Gregor Hendel, hendel@zib.de – SCIP Introduction∀e ∈ E

7/70

TSP – Integer Programming Formulation
Given
xe

• complete graph G = (V , E )• distances de > 0 for all e ∈ E
Binary variables• xe = 1 if edge e is used

min

X

K8
de xe

e∈E

subject toX

xe = 2∀v ∈ Vxe ≥ 2e∈δ(S)∀S ⊂ V , S 6= ∅subtour eliminationxe ∈ {0, 1}∀e ∈ Ee∈δ(v )X

Gregor Hendel, hendel@zib.de – SCIP Introduction

7/70

TSP – Integer Programming Formulation
Given
xe

• complete graph G = (V , E )• distances de > 0 for all e ∈ E
Binary variables• xe = 1 if edge e is used

min

X

K8
distance

de xe

e∈E

subject toX

xe = 2∀v ∈ Vxe ≥ 2∀S ⊂ V , S 6= ∅e∈δ(v )Xe∈δ(S)xe ∈ {0, 1}

Gregor Hendel, hendel@zib.de – SCIP Introduction∀e ∈ E

7/70

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, hendel@zib.de – SCIP Introduction

8/70

TSP – Constraint Programming Formulation

8
7

Given

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
subject tolength(x1 , . . . , xn )alldifferent(x1 , . . . , xn )xv ∈ {1, . . . , n}Gregor Hendel, hendel@zib.de – SCIP Introduction∀v ∈ V

8/70

What is a Constraint Integer Program?

Constraint Integer Program
Objective function:

min
s.t.

. linear function
Feasible set:
. described by arbitrary constraints

cT x
x ∈F
(xI , xC ) ∈ZI × RC

Remark:• arbitrary objective or variables
modeled by constraints

Variable domains:. real or integer values

Gregor Hendel, hendel@zib.de – SCIP Introduction

9/70

What is a Constraint Integer Program?

Constraint Integer Program
Objective function:

min
s.t.

X

de xe

e∈E
X

xe

=2

∀v ∈ Ve∈δ(v ). linear function
Feasible set:
. described by arbitrary constraints
Variable domains:. real or integer values

Gregor Hendel, hendel@zib.de – SCIP Introduction

nosubtour(x)xe∈ {0, 1}∀e ∈ E(CIP formulation of TSP)

Single nosubtour constraint rules
out subtours (e.g. by domain propagation). It may also separate subtour elimination inequalities.

9/70

Mixed-Integer Nonlinear Programs (MINLPs)

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

0
200

10

100

200

5

0
−200

−1
−1

300
200

0

1
1

convex orGregor Hendel, hendel@zib.de – SCIP Introduction

nonconvex

10/70

Application: Data Classification

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

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

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

∀i
∀i

b∈R

Gregor Hendel, hendel@zib.de – SCIP Introduction

11/70

Constraint Integer Programming• Mixed Integer Programs
MIP

Gregor Hendel, hendel@zib.de – SCIP Introduction

12/70

Constraint Integer Programming• Mixed Integer Programs• SATisfiability problems

MIP
SAT

Gregor Hendel, hendel@zib.de – SCIP Introduction

12/70

Constraint Integer Programming• Mixed Integer Programs• SATisfiability problems• Pseudo-Boolean Optimization

MIP
SAT

Gregor Hendel, hendel@zib.de – SCIP Introduction

PBO

12/70

Constraint Integer Programming• Mixed Integer Programs• SATisfiability problems• Pseudo-Boolean Optimization• Mixed Integer Nonlinear Programs

Gregor Hendel, hendel@zib.de – SCIP Introduction

MIP
SAT

PBO MINLP

12/70

Constraint Integer Programming• Mixed Integer Programs• SATisfiability problems• Pseudo-Boolean Optimization• Mixed Integer Nonlinear Programs

MIP
SAT

PBO MINLPCP• Constraint Programming

Gregor Hendel, hendel@zib.de – SCIP Introduction

12/70

Constraint Integer Programming

CIP• Mixed Integer Programs• SATisfiability problems• Pseudo-Boolean Optimization• Mixed Integer Nonlinear Programs

MIP
SAT

PBO MINLPCP• Constraint Programming• Constraint Integer Programming

Gregor Hendel, hendel@zib.de – SCIP Introduction

12/70

Constraint Integer Programming

CIP• Mixed Integer Programs• SATisfiability problems• Pseudo-Boolean Optimization• Mixed Integer Nonlinear Programs

MIP
SAT

PBO MINLPCP• 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, hendel@zib.de – SCIP Introduction

12/70

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, hendel@zib.de – SCIP Introduction

13/70

Branch-and-boundGregor Hendel, hendel@zib.de – SCIP Introduction

14/70

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
optimizewrite 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, hendel@zib.de – SCIP Introduction

15/70

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, hendel@zib.de – SCIP Introduction

16/70

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, hendel@zib.de – SCIP Introduction

17/70

Operational Stages

Init

Problem

Init Solve

Transforming

Free Transform

Gregor Hendel, hendel@zib.de – SCIP Introduction

Presolving

SolvingFree Solve

18/70

Operational Stages

Init

Problem

Init Solve

Transforming

Presolving

Free TransformSolvingFree Solve• Basic data structures are allocated and initialized.
• User includes required plugins (or just takes default plugins).

Gregor Hendel, hendel@zib.de – SCIP Introduction

18/70

Problem Specification

Init

Problem

Init Solve

Transforming

Presolving

Free TransformSolvingFree Solve• User creates and modifies the original problem instance.
• Problem creation is usually done in file readers.

Gregor Hendel, hendel@zib.de – SCIP Introduction

19/70

Define Variables (LOP Example)

SCIP_VAR * var ;SCIP_CALL (// return value macro
SCIPcreateVar (scip ,// SCIP pointer& var ,// save in variable" varname " ,// pass variable name0.0 ,// lower bound1.0 ,// upper boundlength ,// 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, hendel@zib.de – SCIP Introduction

20/70

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 " ,// namenvar ,// 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, hendel@zib.de – SCIP Introduction

21/70

Transformation

Init

Problem

Init Solve

Transforming

Presolving

Free TransformSolvingFree Solve• Creates a working copy of the original problem.

Gregor Hendel, hendel@zib.de – SCIP Introduction

22/70

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, hendel@zib.de – SCIP Introduction

23/70

Presolving

Init

Problem

Init Solve

Transforming

Free Transform

Gregor Hendel, hendel@zib.de – SCIP Introduction

Presolving

SolvingFree Solve

24/70

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:

Dual Reductions:• based on feasibility reasoning• no feasible solution is cut off• consider objective function• at least one optimal solution remains

Gregor Hendel, hendel@zib.de – SCIP Introduction

25/70

Presolving Tips and Parameters
Use display presolvers to list all presolvers of SCIP.
Disable Presolving
Disable all presolving for a models e t p r e s o l v i n g emphasis o f f
Deactivate single techniquess 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 Presolvings 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, hendel@zib.de – SCIP Introduction

26/70

Solving

Init

Problem

Init Solve

Transforming

Free Transform

Gregor Hendel, hendel@zib.de – SCIP Introduction

Presolving

SolvingFree Solve

27/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

28/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

28/70

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 boundTask• improve primal bound• keep comp. effort small• combinations• BBS or BES with plunging• hybrid BES/BBS• interleaved BES/BBS• improve global dual boundGregor Hendel, hendel@zib.de – SCIP Introduction

29/70

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
200000100
best estimate search
bfs
1000000 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. Uses 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, hendel@zib.de – SCIP Introduction

30/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

31/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

31/70

Domain Propagation

x1

x1

x2

x2

x3

⇒

x4

x3
x4

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

Gregor Hendel, hendel@zib.de – SCIP Introduction

32/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

33/70

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, hendel@zib.de – SCIP Introduction

34/70

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, hendel@zib.de – SCIP Introduction

35/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

36/70

Pricing

Pricing• find variable with negative reduced
costs• or prove that there exists none
• typically problem specific• dynamic aging of variables
Branch-and-Price• huge number of variables• problem variable pricer to add
them again• start with subset• early branching possible• add others, when needed• lazy variable bounds

Gregor Hendel, hendel@zib.de – SCIP Introduction

37/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

38/70

Cutting Plane Separation

Techniques• general cuts
• complemented MIR cuts
• Gomory mixed integer cuts
• strong Chvátal-Gomory cuts
• implied bound cuts
• reduced cost strengthening• problem specific cutsTask
• strengthen relaxation• 0-1 knapsack problem• stable set problem• 0-1 single node flow problem• add valid constraints• generate on demand

Gregor Hendel, hendel@zib.de – SCIP Introduction

39/70

Cuts for the 0-1 Knapsack Problem

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

Minimal Cover: C ⊆ N
•

P

•

P

j∈C

5x1 + 6x2 + 2x3 + 2x4 ≤ 8

aj > bj∈C \{i} aj ≤ b∀i ∈ C

Minimal Cover InequalityX
xj ≤ |C | − 1

Minimal cover:C = {2, 3, 4}
Minimal cover inequality:
x2 + x3 + x4 ≤ 2

j∈C

Gregor Hendel, hendel@zib.de – SCIP Introduction

40/70

Separation Tips and Parameters

Disable/Speed up/Emphasize All Separations 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 Techniquess 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, hendel@zib.de – SCIP Introduction

41/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

42/70

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, hendel@zib.de – SCIP Introduction

43/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Constraint Enforcement
Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching• Reduced domain• Added cut• Added constraint• Branched

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cutoff• Infeasible• Feasible
44/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

45/70

Branching Rules

Techniques• branching on variables

Task• most infeasible• least infeasible• random branching• strong branching• pseudocost• reliability• VSIDS• hybrid reliability/inference• branching on constraints• divide into (disjoint)
subproblems• SOS1• SOS2• improve local bounds

Gregor Hendel, hendel@zib.de – SCIP Introduction

46/70

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−−−−−−−−−−−−−−
relpscost
pscostinference
mostinfp r i o r i t y maxdepth m a x b d d i s t−−−−−−−− −−−−−−−− −−−−−−−−−
10000−1
100.0%
2000−1
100.0%
1000−1
100.0%
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, hendel@zib.de – SCIP Introduction

47/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

48/70

Primal Heuristics

Techniques• structure-based• clique• variable bounds• rounding• possibly solve final LP• diving• least infeasible• guided• objective diving
Task• improve primal bound• effective on average• guide remaining search

Gregor Hendel, hendel@zib.de – SCIP Introduction• objective feasibility pump

• Large Neighborhood Search• RINS, local branching• RENS• Adaptive LNS• Completion of partial solutions

49/70

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
AdviceUse emphasis settings. Do not attempt to individually tune heuristics by hand.

Gregor Hendel, hendel@zib.de – SCIP Introduction

50/70

Flow Chart SCIP

Presolving

Stop

Node selection

Domain propagation

Solve LP
Pricing

Conflict analysis

Cuts
Processing
Enforce constraints
Primal heuristics

Branching

Gregor Hendel, hendel@zib.de – SCIP Introduction

51/70

Conflict Analysis

Techniques• Analyze:• Propagation conflicts• Infeasible LPs• Bound-exceeding LPs• Strong branching conflicts• Detection:
Task• Analyze infeasibility• Derive valid constraints• Help to prune other nodes

Gregor Hendel, hendel@zib.de – SCIP Introduction• Cut in conflict graph• LP: Dual ray heuristic• Use conflicts:• Only for propagation• As cutting planes

52/70

Operational Stages

Init

Problem

Init Solve

Transforming

Free Transform

Gregor Hendel, hendel@zib.de – SCIP Introduction

Presolving

SolvingFree Solve

53/70

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, hendel@zib.de – SCIP Introduction

54/70

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, orMultiobjective 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, hendel@zib.de – SCIP Introduction

55/70

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, hendel@zib.de – SCIP Introduction

56/70

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, hendel@zib.de – SCIP Introduction

57/70

Structure of SCIP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpool

var
bound

xprs

spx

xor

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

58/70

Structure of SCIP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpool

var
bound

xprs

spx

xor

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

58/70

Structure of SCIP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpool

var
bound

xprs

spx

xor

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

58/70

Plugin based design
SCIP core• branching tree

• solution pool

• clique table• variables• cut pool

• implication graph• conflict analysis• statistics• ...

Gregor Hendel, hendel@zib.de – SCIP Introduction

59/70

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, hendel@zib.de – SCIP Introduction

59/70

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, hendel@zib.de – SCIP Introduction

59/70

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, hendel@zib.de – SCIP Introduction

59/70

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, hendel@zib.de – SCIP Introduction

60/70

A closer look: branching rules
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpool

var
bound

xprs

spx

xor

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

61/70

default

A closer look: branching rules

simplerounding

Conflictallfullstrongbounddisjunc.

count
sols

full
strong

infer
ence

cumu
lativeBranchindi
catorintegralknap
sack

shifting

leastinf
relps
cost

mostinf
randompscostglinearGregor Hendel, hendel@zib.de – SCIP Introduction

61/70

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, hendel@zib.de – SCIP Introduction

62/70

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, hendel@zib.de – SCIP Introduction

63/70

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, hendel@zib.de – SCIP Introduction

64/70

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, hendel@zib.de – SCIP Introduction

64/70

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

Gregor Hendel, hendel@zib.de – SCIP Introduction• statistics

64/70

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, hendel@zib.de – SCIP Introduction

65/70

Default Plugins
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialCutpool

var
bound

xprs

spx

xor

count
sols

LP

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

rootsoldivingfull
strong

infer
ence

cumu
lativeBranchindi
catorsetppcrounding

shifting

allfullstrongbounddisjunc.
and

sos1

qso

simplerounding

Conflict

sos2

shift&
prop

trysoldefault
default

rens

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

66/70

Extending SCIP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip
trivialredcostzpl

ccg

strong
cg

zero
half

implics

dualfix

impliedbounds intobj

flow
cover

rlp

fix

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

vboundguideddivingint
shifting
local
branchingdinsmutation

restartdfs···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptzi rounddfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpool

var
bound

xprs

spx

xor

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

67/70

Extending SCIP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip

impliedbounds intobj

flow
cover

rlp

fix

default
ccg

redcostdefault
default

implics

dualfix

strongcg

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixand
infer
cross
over

default

guideddivingint
shifting
local
branchingdinsmutation

default···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingactcons
divingSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptdefault

dfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpoolvar
bound

defaultspx

default

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

shifting

infer
ence

cumu
lativeBranchindi
catorsetppcrootsoldivingfull
strong

and
count
sols

rens

rounding

allfullstrongbounddisjunc.

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

67/70

Extending SCIP: TSP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip

impliedbounds intobj

flow
cover

rlp

fix

default
redcostdefault

tsp

default

implics

dualfix

strongcg

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixandinfer
2-Opt

default

guideddivingint
shifting
local
branchingdinsmutation

default···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
divingfarthest
insertSCIP

Nodeselector

estimate

PrimalHeuristic

octaneoneoptdefault

dfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpoolvar
bound

default

spx

Conflictdefault

count
sols

Constraint
Handler

soc

none

clp
msk

cpx

integral
knap
sack

quadr
atic

orbi
tope

or

rootsoldivingshifting

fullstrong

infer
ence

cumu
lativeBranchindi
catorsetppcrensrounding

allfullstrongsubtour

sos2

qso

simplerounding

sol
found

bound
disjunc.

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

67/70

Extending SCIP: Coloringmps

opb
gomoryppm

lp

Readerintto
binaryprobing

odd
cycle
Separator

redcostcoloring

default

col

rapid
learn

cliquesos

csol

default

mcf

cmir
sol

cnf

impliedbounds intobj

flow
cover

rlp

fix

default

implics

dualfix

strongcg

PresolverTreefracdiving

pseudoobj

PricerImplications

bound
shift

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixandinfer
2-Opt

default

guideddivingint
shifting
local
branchingdinsmutation

default···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
diving

init

SCIP

Node
selector

estimate

PrimalHeuristic

octaneoneoptdefault

dfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpoolvar
bound

defaultspx

default

store
Graph

Constraint
Handler

soc

none

clp
msk

cpx

orbi
tope

or

shifting

infer
ence

cumu
lativeintegral
knap
sack

quadr
atic

rootsoldivingstrong
Ryan&
FosterBranchindi
catorsetppcrensrounding

Ryan&
Fosterbounddisjunc.

count
sols

sos2

qso

simplerounding

Conflict

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

67/70

Extending SCIP: STP
mps

opb
gomoryppm

lp

Readerintto
binaryprobing

mcf

odd
cycle

cmir

Separator

sol

cnf

rapid
learn

cliquesos

cip

impliedbounds intobj

flow
cover

rlp

fix

default
redcostdefault

stp

default

implics

dualfix

strongcg

PresolverTreefracdiving

pseudoobj

PricerImplications

stp

Propa
gator

intdivinglinesearch
divingfeaspump

root
redcostfixandinfer

default

local

guideddivingint
shifting
local
branchingdinsmutation

default···

hybrid
estim

Relax

coef
divingsubnlpobjpscost
diving

TM

SCIP

Node
selector

estimate

PrimalHeuristic

octaneoneoptdefault

dfs
Display

pscostdivingveclendivingVariablebfs

Dialogdefault

under
cover

Event

twooptrins

trivialdefault

Cutpoolvar
bound

default

spx

Conflictstp

default

count
sols

sos2

qso

Constraint
Handler

soc

none

clp
msk

cpx

orbi
tope

rootsoldivingshifting

fullstrong

infer
ence

cumu
lativeintegral
knap
sack
or

rens

rounding

allfullstrongBranchindi
catorsetppcquadr
atic

simplerounding

sol
found

bound
disjunc.

sos1

LP

shift&
prop

trysoldefault

leastinf
relps
cost

mostinf
randompscostlinkinglinearlogicor

Gregor Hendel, hendel@zib.de – SCIP Introduction

67/70

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, hendel@zib.de – SCIP Introduction

68/70

SCIP Optimization Suite• Toolbox for generating and solving constraint integer programs• free for academic use, available in source code

Gregor Hendel, hendel@zib.de – SCIP Introduction

69/70

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, hendel@zib.de – SCIP Introduction

69/70

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, hendel@zib.de – SCIP Introduction

70/70