[PDF] Introduction to SCIP 26 sept. 2018 SCIP (Solving

View - Download Introduction to SCIP

Previous PDF

Next PDF

SCIP Introduction Sep. 26, 2018

Time Schedule

9:30{11:00Introduction & Overview (1)

11:00{11:30 Break11:30{12:30Introduction & Overview (2)

12:30{14:00 Lunch Break14:00{15:30Programming Exercises with PySCIPOpt (rst steps)

15:30{16:00 Break16:00{17:30Programming Exercises With PySCIPOpt (more realistic examples)

SCIP Introduction at the 3rd IMI-ISM-ZIB Workshop, Tokio, Japan Gregor Hendel, hendel@zib.de { SCIP Introduction1/71

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 (con

ict 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 underhttp://scip.zib.de!Gregor Hendel, hendel@zib.de { SCIP Introduction2/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-Nurnberg: 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 Introduction3/71

Outline

SCIP {

S olving C onstraint I nteger P rogramsConstraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suitehttp://scip.zib.de

Gregor Hendel, hendel@zib.de { SCIP Introduction4/71

Outline

SCIP {

S olving C onstraint I nteger P rogramsConstraint Integer Programming

The Solving Process of SCIP

Extending SCIP by Plugins

The SCIP Optimization Suitehttp://scip.zib.de

Gregor Hendel, hendel@zib.de { SCIP Introduction5/71

An example: the Traveling Salesman Problem

Denition (TSP)

Given a complete graph

G= (V;E) and distancesdefor

alle2E:

Find a

Hamiltonian cycle

(cycle containing all nodes, tour) of minimum length.K

8Gregor Hendel, hendel@zib.de { SCIP Introduction6/71

An example: the Traveling Salesman Problem

Denition (TSP)

Given a complete graph

G= (V;E) and distancesdefor

alle2E:

Find a

Hamiltonian cycle

(cycle containing all nodes, tour) of minimum length.K

8Gregor Hendel, hendel@zib.de { SCIP Introduction6/71

An example: the Traveling Salesman Problem

Denition (TSP)

Given a complete graph

G= (V;E) and distancesdefor

alle2E:

Find a

Hamiltonian cycle

(cycle containing all nodes, tour) of minimum length.Gregor Hendel, hendel@zib.de { SCIP Introduction6/71

What is a Constraint Integer Program?

Mixed Integer Program

Objective function:

.linearfunction

Feasible set:

.described bylinea rconstraints

Variable domains:

.real or integervalues mincTx s:t:Axb (xI;xC)2?I?CConstraint Program

Objective function:

.arbitraryfunction

Feasible set:

.given bya rbitraryconstraints

Variable domains:

.arbitrary(usually nite) minc(x) s:t:x2F (xI;xN)2?IXGregor Hendel, hendel@zib.de { SCIP Introduction7/71

TSP { Integer Programming Formulation

Given complete graphG= (V;E) distancesde>0 for alle2E

Binary variables

xe= 1 if edgeeis usedx eK 8min X e2Ed exe subject to X e2(v)x e= 28v2V X e2(S)x e28SV;S6=? x e2 f0;1g 8e2EGregor Hendel, hendel@zib.de { SCIP Introduction8/71

TSP { Integer Programming Formulation

Given complete graphG= (V;E) distancesde>0 for alle2E

Binary variables

xe= 1 if edgeeis usedx eK 8min X e2Ed exe subject to X e2(v)x e= 28v2V X e2(S)x e28SV;S6=? x e2 f0;1g 8e2EGregor Hendel, hendel@zib.de { SCIP Introduction8/71

TSP { Integer Programming Formulation

Given complete graphG= (V;E) distancesde>0 for alle2E

Binary variables

xe= 1 if edgeeis usedx eK 8min X e2Ed exe subject to X e2(v)x e= 28v2V X e2(S)x e28SV;S6=? x e2 f0;1g 8e2Enode degree Gregor Hendel, hendel@zib.de { SCIP Introduction8/71

TSP { Integer Programming Formulation

Given complete graphG= (V;E) distancesde>0 for alle2E

Binary variables

xe= 1 if edgeeis usedx eK 8min X e2Ed exe subject to X e2(v)x e= 28v2V X e2(S)x e28SV;S6=? x e2 f0;1g 8e2Esubtour elimination Gregor Hendel, hendel@zib.de { SCIP Introduction8/71

TSP { Integer Programming Formulation

Given complete graphG= (V;E) distancesde>0 for alle2E

Binary variables

xe= 1 if edgeeis usedx eK 8min X e2Ed exe subject to X e2(v)x e= 28v2V X e2(S)x e28SV;S6=? x e2 f0;1g 8e2Edistance Gregor Hendel, hendel@zib.de { SCIP Introduction8/71

TSP { Constraint Programming Formulation

Given complete graphG= (V;E) for eache2Ea distancede>0

Integer variables

xvposition ofv2Vin tourx vK 812
3 4 5678
min length(x1;:::;xn) subject to alldierent(x1;:::;xn) x v2 f1;:::;ng 8v2VGregor Hendel, hendel@zib.de { SCIP Introduction9/71

TSP { Constraint Programming Formulation

Given complete graphG= (V;E) for eache2Ea distancede>0

Integer variables

xvposition ofv2Vin tourx vK 812
3 4 5678
min length(x1;:::;xn) subject to alldierent(x1;:::;xn) x v2 f1;:::;ng 8v2VGregor Hendel, hendel@zib.de { SCIP Introduction9/71

What is a Constraint Integer Program?

Constraint Integer Program

Objective function:

.linearfunction

Feasible set:

.described bya rbitraryconstraints

Variable domains:

.real or integervalues mincTx s:t:x2F (xI;xC)2?I?CRemark: arbitrary objective or variables modeled by constraintsGregor Hendel, hendel@zib.de { SCIP Introduction10/71

What is a Constraint Integer Program?

Constraint Integer Program

Objective function:

.linearfunction

Feasible set:

.described bya rbitraryconstraints

Variable domains:

.real or integervalues min X e2Ed exe s:t:X e2(v)x e= 28v2V nosubtour(x) x e2 f0;1g 8e2E (CIP formulation of TSP)

Single nosubtour constraint rules

out subtours (e.g. by domain prop- agation). It may also separate sub- tour elimination inequalities.Gregor Hendel, hendel@zib.de { SCIP Introduction10/71

Mixed-Integer Nonlinear Programs (MINLPs)

mincTx s.t.gk(x)08k2[m] x i2Z8i2 I [n] x i2[`i;ui]8i2[n]

The functionsgk2C1([`;u];R) can be1111510

convex o r0100200300 0200

2000200

nonconvex Gregor Hendel, hendel@zib.de { SCIP Introduction11/71

Application: Data Classication

Support Vector Machine, e.g., withramp loss .min

wTw2 +Cn n X i=1(i+ 2(1zi)) s.t.zi(yi(wTxi+b)1 +i)08i i2[0;2];zi2 f0;1g 8i w2Rd;b2RGregor Hendel, hendel@zib.de { SCIP Introduction12/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Constraint Integer Programming

MixedIntegerProgramsSATisability problemsPseudo-BooleanOptimizationMixedIntegerNonlinearProgramsConstraintProgrammingConstraintIntegerProgrammingCPCIP

MINLPPBOMIP

SAT

Relation to CP and MIP

Every MIP is a CIP.\MIP(CIP"

Every CP over a nite domain space is a CIP.\FD(CIP"Gregor Hendel, hendel@zib.de { SCIP Introduction13/71

Outline

SCIP {

S olvingquotesdbs_dbs10.pdfusesText_16

[PDF] introduction au café-philo - Reseau

[PDF] Introduction au calcul scientifique pour les EDP de la

[PDF] INTRODUCTION AU CALCUL TENSORIEL - Géométrie

[PDF] Introduction au calcul tensoriel 4h - Géométrie

[PDF] INTRODUCTION AU CHAMANISME AMÉRINDIEN Eric Navet

[PDF] Introduction au Chi Gong - France

[PDF] introduction au cinéma allemand

[PDF] Introduction au CMS d`entreprise TYPO3 - Jean

[PDF] Introduction au contenu web dynamique - Nouvelles Locales

[PDF] INTRODUCTION au CONTRAT de SEJOUR - Un Hôtel

[PDF] Introduction au Coran

[PDF] Introduction au cours de contrôle de gestion 2

[PDF] Introduction au cours développement local L2

[PDF] Introduction au cracking By Mr_roW - Anciens Et Réunions

[PDF] Introduction au Data-Mining