Parallel Discrepancy-based Search
T. Moisan, J. Gaudreault, C.-G. Quimper
Université Laval, FORAC research consortium

February 21th 2014

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

1 / 57

Upsides of Parallelization
Parallel computing is a growing domain.
Governments and industries are intensively investing in it.
It is a huge opportunity for constraint programming.
It can lead to unpreceded performances.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

2 / 57

Downsides of Parallelization
Parallelization is hard.
Speedup can stall very fast due to communication.
It is difficult to reproduce in a parallel environment the search strategies
that work well sequentially.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

3 / 57

Outline1

Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

4 / 57

Constraint programming

Uses variables with a finite domain;
Uses specific constraints to modelize the problem:
IIAll-different: variables must have different values;
Regular: variables must follow a defined regular expression.

Each constraint includes a specialized algorithm to filter the search space;
Can include an objective function.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

5 / 57

Exemple

0ZQZ3L0Z0
20Z0L
1ZQZ0
4x1x2x3

dom(x1 ) = {1, 2, 3, 4}
dom(x2 ) = {1, 2, 3, 4}
dom(x3 ) = {1, 2, 3, 4}
dom(x4 ) = {1, 2, 3, 4}
T. Moisan, J. Gaudreault, C.-G. Quimper

x40L0Z
Z0ZQ
2QZ0Z
1Z0L0
4
3x1x2x3x4xi 6= xj ∀i < jxj − xi 6= j − i ∀i < jxj − xi 6= i − j ∀i < jParallel Discrepancy-based Search

February 21th 2014

6 / 57

Espace de recherche
Ensemble des assignations partielles des variablesI

Cet espace est typiquement représenté par un arbre n-aire.
0Z0Z
Z0Z00Z0Z
1Z0Z0
40Z0Z
3Z0Z020Z0Z
1L0Z0
4x1x2x3

32x1x2x4x3x40Z0Z
Z0Z0
QZ0Z
1Z0Z0
430L0Z
Z0Z0
QZ0Z
1Z0Z0
4

2x1x2xxx3

32x4x10Z0Z
ZQZ0
20Z0Z
1
L0Z0

0L0Z
Z0Z0
20Z0Z
1
L0Z0

4433x1x2x3x4x1x2x3xxx0L0Z
Z0Z0
QZ0Z
1Z0L0
2x40L0Z
3Z0Z0
20ZQZ
1L0Z0xT. Moisan, J. Gaudreault, C.-G. Quimperxx2x4

34x1x34x1xx2xx3x4xx

Parallel Discrepancy-based Searchxx2x3x4x0L0Z
Z0ZQ
QZ0Z
1Z0L0
4
32x1x2x3x4

February 21th 2014

7 / 57

Outline1

Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 20148 / 57

Depth-first Search (DFS)The value ordering heuristic function orders the children of a node from themost likely one to lead to a solution to the least likely one.

1

T. Moisan, J. Gaudreault, C.-G. Quimper

2345

6

Parallel Discrepancy-based Search

78

February 21th 2014

9 / 57

Depth-first Search (DFS)1

T. Moisan, J. Gaudreault, C.-G. Quimper

2345

6

Parallel Discrepancy-based Search

78February 21th 2014

10 / 57

Depth-first Search (DFS)

1T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201411 / 57

Depth-first Search (DFS)1

T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201412 / 57

Depth-first Search (DFS)1

T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201413 / 57

Depth-first Search (DFS)

1T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201414 / 57

Depth-first Search (DFS)

1T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201415 / 57

Depth-first Search (DFS)1

T. Moisan, J. Gaudreault, C.-G. Quimper

23456

Parallel Discrepancy-based Search

78February 21th 201416 / 57

Outline
1Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201417 / 57

Limited Discrepancy Search (LDS)
Harvey and Ginsberg (1995)

The value ordering heuristic function orders the children of a node from themost likely one to lead to a solution to the least likely one. A discrepancy is adeviation from the first choice of the value ordering heuristic.

01121

2

2

3

LDS proposes to visit the leaves in increasing order of discrepancy.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201418 / 57

Limited Discrepancy Search (LDS)
Harvey and Ginsberg (1995)

The value ordering heuristic function orders the children of a node from themost likely one to lead to a solution to the least likely one. A discrepancy is adeviation from the first choice of the value ordering heuristic.

01121

2

2

3

LDS proposes to visit the leaves in increasing order of discrepancy.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201419 / 57

LDS Iterations 0 (0 discrepancy)

01T. Moisan, J. Gaudreault, C.-G. Quimper

12

1

Parallel Discrepancy-based Search

223February 21th 2014

20 / 57

LDS Iterations 1 (1 discrepancy)

01T. Moisan, J. Gaudreault, C.-G. Quimper

12

1

Parallel Discrepancy-based Search

223

February 21th 2014

21 / 57

LDS Iterations 2 (2 discrepancies)

01T. Moisan, J. Gaudreault, C.-G. Quimper

121

Parallel Discrepancy-based Search

223February 21th 201422 / 57

LDS Iterations 3 (3 discrepancies)

01

T. Moisan, J. Gaudreault, C.-G. Quimper

12

1

Parallel Discrepancy-based Search

22

3February 21th 2014

23 / 57

LDS Overhead versus DFS

Nodes in a binary tree with n variables: 2 · 2n − 1
Node visits with a DFS: 2 · 2n − 1
Node visits with a LDS: 4 · 2n − n − 3
By the time DFS visits the entire tree, LDS will visit half of the leaves.
The leaves that LDS visits are those that have fewer than n/2
discrepancies.
If the value ordering heuristic is as good as a random heuristic, LDS finds
a solution by the time DFS completes.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201424 / 57

Outline1

Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

25 / 57

Portfolio

Il s’agı̂t d’une course entre les processeurs pour obtenir une solution.
Chaque processeur recherche une solution avec un algorithme qui lui est
propreLes processeurs peuvent s’aider en échangeant des informations.
Il est difficile d’étendre à un nombre arbitraire de processeurs.
Il faut définir des paramètres de recherche pour chaque processeur.
Ces paramètres sont souvent établis manuellement.
I La paramétrisation est fortement lié au problème à résoudre.

II

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

26 / 57

Work-stealing
Xie et Davenport
Processeur 1

Processeur 2

A

BX

YCDZ

V

E

T. Moisan, J. Gaudreault, C.-G. Quimper

W

Parallel Discrepancy-based Search

February 21th 201427 / 57

Work-stealing
Processeur 1

Processeur 2

AB

X

Y

CDZ

V

E

T. Moisan, J. Gaudreault, C.-G. Quimper

W

Parallel Discrepancy-based Search

February 21th 201428 / 57

Work-stealing

Processeur 1Processeur 2

ABX

YCDZ

VE

T. Moisan, J. Gaudreault, C.-G. Quimper

Je n'ai plusde travail.

W

Parallel Discrepancy-based Search

February 21th 201429 / 57

Work-stealing
Processeur 1

Processeur 2CA

DBX

YEZ

V

W

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201430 / 57

Work-stealing
Processeur 1

A

Processeur 2

BX

YE

Z

VCW

DT. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201431 / 57

Work-stealing
Processeur 1

A

Processeur 2

BXYEZVCW

DT. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201432 / 57

Division de l’espace de recherche

Approche très courante
Divise théoriquement la charge de travail également
Peu probable que les sous-arbres soient de même tailleII

Ne peut pas être utilisé sur un grand nombre de processeurs
Problème NP-Difficile

Si les sous-arbres ne sont pas de même tailleIILes processeurs n’auront pas la même charge de travail
La durée totale de la tâche sera plus longue

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201433 / 57

Outline1

Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201434 / 57

Our Objectives

Having a search strategy that performs well sequentially, we want toparallelize it with four main goals in mind:
Search strategy preservation
Workload balancing
I Robustness
I No communication
II

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201435 / 57

Intuition behind PDS
Each leaf is assigned to a processor.
The leaves are implicitly assigned in a round-robin fashion.
To split the task, let’s say that p1 takes odd leaves and p2 the even leaves.

12T. Moisan, J. Gaudreault, C.-G. Quimper

3546

Parallel Discrepancy-based Search

78February 21th 201436 / 57

Intuition behind PDS
Each leaf is assigned to a processor.
The leaves are implicitly assigned in a round-robin fashion.
To split the task, let’s say that p1 takes odd leaves and p2 the even leaves.

p1
p2

1

2T. Moisan, J. Gaudreault, C.-G. Quimper

3546

Parallel Discrepancy-based Search

78February 21th 201437 / 57

PDS overview

p1
p2
p 1 & p2
12

3T. Moisan, J. Gaudreault, C.-G. Quimper

5467

Parallel Discrepancy-based Search

8February 21th 201438 / 57

PDS overview

p1
p2
p 1 & p2
12

3

T. Moisan, J. Gaudreault, C.-G. Quimper

546

7

Parallel Discrepancy-based Search

8February 21th 201439 / 57

PDS overview

p1
p2
p 1 & p2
12

3

T. Moisan, J. Gaudreault, C.-G. Quimper

546

7

Parallel Discrepancy-based Search

8February 21th 2014

40 / 57

Implementing PDS
p : its processor idρ : the number of processors
n : the number of variables in the subtree
k : the number of required discrepanciesl : the processor id implicitly assigned to the leftmost leaf
The processor will branch in the subtree if (p − l ) mod ρ <nk

nkl

(l + 1) mod ⇢T. Moisan, J. Gaudreault, C.-G. Quimper(l + 2) mod ⇢...

Parallel Discrepancy-based Search(l + nk ) mod ⇢February 21th 201441 / 57

Branching in PDS

n 1kl

T. Moisan, J. Gaudreault, C.-G. Quimpern 1k 1l + nk 1

mod ⇢Parallel Discrepancy-based Search

February 21th 201442 / 57

Outline1Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201443 / 57

PDS overhead versus LDSProcessors
123...

ρNode visits
4 · 2n − n − 3
5 · 2n − 2n − 45.75 · 2n − 3n − 5...
2n + 2n ∑ni=1 ∑ik =0 21i min(ρ, ki )T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

Overhead
25%
43%
...

Speedup
1.61
2.08
...

February 21th 201444 / 57

Speedup for some number of processors

1600

n =11 variables

1400

Speedup

1200
1000
800
600
400
20000

1000

T. Moisan, J. Gaudreault, C.-G. Quimper

2000

3000

4000

Number of processors (ρ)

Parallel Discrepancy-based Search

5000

6000

February 21th 201445 / 57

Speedup for some number of processors

1600
1400

Speedup1200

n =11 variables
n =15 variables
n =17 variables
n =20 variables
n =30 variables

1000
80060040020000

1000

T. Moisan, J. Gaudreault, C.-G. Quimper

2000

3000

4000

Number of processors (ρ)

Parallel Discrepancy-based Search

5000

6000

February 21th 201446 / 57

Average computation time to find a solution according to thenumber of variables

Average computation time (number of visited nodes)

35000

PDS ρ =1

30000
25000
20000
15000
10000
5000
00

2

T. Moisan, J. Gaudreault, C.-G. Quimper

468
10
Nb variables

Parallel Discrepancy-based Search

121416
February 21th 2014

47 / 57

Average computation time to find a solution according to thenumber of variables

Average computation time (number of visited nodes)

35000
30000
25000
20000

PDS ρ =1
PDS ρ =2PDS ρ =4PDS ρ =16PDS ρ =32PDS ρ =64

15000
10000
5000002T. Moisan, J. Gaudreault, C.-G. Quimper

46810
Nb variables

Parallel Discrepancy-based Search

121416
February 21th 2014

48 / 57

Balancing
Theorem
Let n be the number of variables in the problem. If a branch is cut from thesearch tree, the number of leaves removed from the workload of eachprocessor differs by at most n.

01121223p1 p2 p1 p1 p2 p2 p1 p2

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201449 / 57

Outline
1Constraint programming

2

Depth-first Search (DFS)

3

Limited Discrepancy Search (LDS)

4

Parallel computing in constraint programming

5

Parallel Discrepancy-based Search (PDS)

6

Theoretical and statistical analysis

7

Experimentations with an industrial case

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

50 / 57

Planning and scheduling wood finishing operations
We minimize order lateness.
The production is done with one-to-many operations.
There is multiple ways to produce the same product.
Output A

Input X

Operation 1

Output B

Output C

Input Y

Operation 2

Output D

Output E

There are setup constraints that restrict sequencing of the operations.
This is a problem for which LDS was efficient thanks to a specialized value
ordering heuristic (Gaudreault et.al (2010)).

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 2014

51 / 57

Instances from a Canadian Forest-Product Company

We worked with industrial instances:65,142 variables
50,238 constraints
42 discrete decision variables whose domains have cardinality 6I
I

Used LDS/PDS to fix those variables.
Once the discrete decision variables are known, the remaining continuous
variables define a linear program that can be easily solved to optimality.

4200 continuous decision variables
I

Linear program solved with Cplex.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201452 / 57

Results
2.2 1e7

PDS ρ =1

2.0

objective value

1.8
1.6
1.4
1.2
1.00500T. Moisan, J. Gaudreault, C.-G. Quimper

1000

1500
2000
time (s)Parallel Discrepancy-based Search

2500

3000

3500

February 21th 2014

53 / 57

Results
2.2 1e7

PDS ρ =1
PDS ρ =512
PDS ρ =1024
PDS ρ =2048
PDS ρ =4096

2.0

objective value

1.8
1.6
1.4
1.2
1.00

500

T. Moisan, J. Gaudreault, C.-G. Quimper

1000

1500
2000
time (s)Parallel Discrepancy-based Search

2500

3000

3500

February 21th 2014

54 / 57

Results

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201455 / 57

Results

60 %T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201456 / 57

Conclusion

Theoretical analysis of DFS versus LDS
Parallel Discrepancy-based Search (PDS)LDS search strategy preservation
No communication
I Intrinsic load balancing
I Robust to hardware failures
II

Theoretical analysis of this parallelization.
Experimental results on large industrial instances with up to 4096
processors.

T. Moisan, J. Gaudreault, C.-G. Quimper

Parallel Discrepancy-based Search

February 21th 201457 / 57