All meals for a dollar and other vertex
enumeration problems
David Avis
Kyoto University and McGill University
http://cgm.cs.mcgill.ca/∼avis

October 18, 2018

Outline

Vertex Enumeration

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Outline of talk

Diet problem• Situation: You need to choose some food in the supermarket

to feed yourself properly for just $1 per day.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Diet problem• Situation: You need to choose some food in the supermarket

to feed yourself properly for just $1 per day.
• Decison variables: How much of each product you will buy.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Diet problem• Situation: You need to choose some food in the supermarket

to feed yourself properly for just $1 per day.
• Decison variables: How much of each product you will buy.
• Constraints: There are minimum daily requirements forcalories, vitamins, calcium, etc. There is a maximum amountof each food you can eat.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Diet problem• Situation: You need to choose some food in the supermarket

to feed yourself properly for just $1 per day.
• Decison variables: How much of each product you will buy.
• Constraints: There are minimum daily requirements forcalories, vitamins, calcium, etc. There is a maximum amountof each food you can eat.
• Objective Eat for less than $1.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Sample data

Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

The decision variables are x1 , x2 , ..., x6 .
Fractional servings are allowed.
From Linear Programming, Vasek Chvátal, 1983

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchLinear programming formulation for diet problem
Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

min z = 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6
s.t.

110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6

≥

2000

4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6≥

55

2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6≥

800

0 ≤ x1 ≤ 4,

0 ≤ x2 ≤ 3,

0 ≤ x3 ≤ 2,

0 ≤ x4 ≤ 8,

0 ≤ x5 ≤ 2,

0 ≤ x6 ≤ 2

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchLinear programming solution

Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchLinear programming solution

Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

• x1 = 4(oatmeal) x4 = 4.5(milk) x5 = 2(pie) cost=92.5 ¢

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchLinear programming solution

Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

• x1 = 4(oatmeal) x4 = 4.5(milk) x5 = 2(pie) cost=92.5 ¢• Where are the chicken, eggs and pork?

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchLinear programming solution

Food
x1
x2
x3
x4
x5
x6

Oatmeal
ChickenEggs
Milk
Cherry Pie
Pork w. beans
Min. Daily Amt.

Serv.
Size
28g
100g
2 large
237ml
170g
260g

Energy(kcal)
110
205
160
160
420
260
2000

Protein
(g)
4
32
13
8
4
14
55

Calcium
(mg)
2
12
54
285
22
80
800

Price
¢
3
24
13
9
20
19

• x1 = 4(oatmeal) x4 = 4.5(milk) x5 = 2(pie) cost=92.5 ¢• Where are the chicken, eggs and pork?
• Do I have to eat the same food every day?

Max
Serv.
4
3
2
8
2
2

Outline

Vertex Enumeration

Reverse Search

Problems with the solution

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Problems with the solution• Many desirable items were not included in the optimum

solution

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Problems with the solution• Many desirable items were not included in the optimum

solution• We obtained a unique optimum solution, but ...

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Problems with the solution• Many desirable items were not included in the optimum

solution• We obtained a unique optimum solution, but ...
• ... people (and managers) like to make choices!

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Problems with the solution• Many desirable items were not included in the optimum

solution• We obtained a unique optimum solution, but ...
• ... people (and managers) like to make choices!
• Ask the right question !

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Problems with the solution• Many desirable items were not included in the optimum

solution• We obtained a unique optimum solution, but ...
• ... people (and managers) like to make choices!
• Ask the right question !
• What are all the meals I can eat for at most $1?

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

All meals for a dollar
Replace the objective function by an inequality:
3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6 ≤ 100
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800
0 ≤ x1 ≤ 4,

0 ≤ x2 ≤ 3,

0 ≤ x3 ≤ 2,

0 ≤ x4 ≤ 8,

0 ≤ x5 ≤ 2,

0 ≤ x6 ≤ 2

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

All meals for a dollar
Replace the objective function by an inequality:
3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6 ≤ 100
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800
0 ≤ x1 ≤ 4,

0 ≤ x2 ≤ 3,

0 ≤ x3 ≤ 2,

0 ≤ x4 ≤ 8,

0 ≤ x5 ≤ 2,

0 ≤ x6 ≤ 2• Any solution to these inequalities is a meal for under $1

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

All meals for a dollar
Replace the objective function by an inequality:
3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6 ≤ 100
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800
0 ≤ x1 ≤ 4,

0 ≤ x2 ≤ 3,

0 ≤ x3 ≤ 2,

0 ≤ x4 ≤ 8,

0 ≤ x5 ≤ 2,

0 ≤ x6 ≤ 2• Any solution to these inequalities is a meal for under $1• But this is just a restatement of the problem .......

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

All meals for a dollar
Replace the objective function by an inequality:
3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6 ≤ 100
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800
0 ≤ x1 ≤ 4,

0 ≤ x2 ≤ 3,

0 ≤ x3 ≤ 2,

0 ≤ x4 ≤ 8,

0 ≤ x5 ≤ 2,

0 ≤ x6 ≤ 2• Any solution to these inequalities is a meal for under $1• But this is just a restatement of the problem .......
• ... how do I find these solutions?

Outline

Vertex Enumeration

Reverse Search

A more useful solution

D. Avis, M Gill Univ.

All menus for a $1
All (17) Extreme
Solutions to the Diet Problem with Budget $1.00
Cost Oat- Chi ken Eggs Milk Cherry Pork
meal
Pie
Beans
92.5 4.
00
4.5 2.
097.3 4.
0
0
8.
0.67
0
98.6 4.
002.23 2.
1.40
100. 1.65 006.12 2.
0100. 2.81 0
0
8.
0.98
0
100. 3.74 002.20 2.
1.53
100. 4.
002.18 1.88
1.62
100. 4.
002.21 2.
1.48
100. 4.
005.33 2.
0100. 4.
0
0
8.
0.42
0.40
100. 4.
0
0
8.
0.80
0
100. 4.
00.50 8.
0.48
0100. 4.
01.88 2.63 2.
0100. 4.
0.17
02.27 2.
1.24
100. 4.
0.19
0
8.
0.58
0
100. 4.
0.60
03.73 2.
0100. 4.
01.03 2.21 2.
0.78

Parallel Reverse Search1Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

A more useful solution
D. Avis, M Gill Univ.

All menus for a $1
All (17) Extreme
Solutions to the Diet Problem with Budget $1.00
Cost Oat- Chi ken Eggs Milk Cherry Pork
meal
Pie
Beans
92.5 4.
00
4.5 2.
097.3 4.
0
0
8.
0.67
0
98.6 4.
002.23 2.
1.40
100. 1.65 006.12 2.
0100. 2.81 0
0
8.
0.98
0
100. 3.74 002.20 2.
1.53
100. 4.
002.18 1.88
1.62
100. 4.
002.21 2.
1.48
100. 4.
005.33 2.
0100. 4.
0
0
8.
0.42
0.40
100. 4.
0
0
8.
0.80
0
100. 4.
00.50 8.
0.48
0100. 4.
01.88 2.63 2.
0100. 4.
0.17
02.27 2.
1.24
100. 4.
0.19
0
8.
0.58
0
100. 4.
0.60
03.73 2.
0100. 4.
01.03 2.21 2.
0.78

1

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

A more useful solution
D. Avis, M Gill Univ.

1

All menus for a $1
All (17) Extreme
Solutions to the Diet Problem with Budget $1.00
Cost Oat- Chi ken Eggs Milk Cherry Pork
meal
Pie
Beans
92.5 4.
00
4.5 2.
097.3 4.
0
0
8.
0.67
0
98.6 4.
002.23 2.
1.40
100. 1.65 006.12 2.
0100. 2.81 0
0
8.
0.98
0
100. 3.74 002.20 2.
1.53
100. 4.
002.18 1.88
1.62
100. 4.
002.21 2.
1.48
100. 4.
005.33 2.
0100. 4.
0
0
8.
0.42
0.40
100. 4.
0
0
8.
0.80
0
100. 4.
00.50 8.
0.48
0100. 4.
01.88 2.63 2.
0100. 4.
0.17
02.27 2.
1.24
100. 4.
0.19
0
8.
0.58
0
100. 4.
0.60
03.73 2.
0100. 4.
01.03 2.21 2.
0.78• Taking convex combinations of rows gives new meals

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

A more useful solution
D. Avis, M Gill Univ.

1

All menus for a $1
All (17) Extreme
Solutions to the Diet Problem with Budget $1.00
Cost Oat- Chi ken Eggs Milk Cherry Pork
meal
Pie
Beans
92.5 4.
00
4.5 2.
097.3 4.
0
0
8.
0.67
0
98.6 4.
002.23 2.
1.40
100. 1.65 006.12 2.
0100. 2.81 0
0
8.
0.98
0
100. 3.74 002.20 2.
1.53
100. 4.
002.18 1.88
1.62
100. 4.
002.21 2.
1.48
100. 4.
005.33 2.
0100. 4.
0
0
8.
0.42
0.40
100. 4.
0
0
8.
0.80
0
100. 4.
00.50 8.
0.48
0100. 4.
01.88 2.63 2.
0100. 4.
0.17
02.27 2.
1.24
100. 4.
0.19
0
8.
0.58
0
100. 4.
0.60
03.73 2.
0100. 4.
01.03 2.21 2.
0.78• Taking convex combinations of rows gives new meals• Eg. Taking half each of the last two rows gives a $1 meal with all foods

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

10

Example in R3(−1, −1 0)(1, −1 , 0)
(1, 1, 0)(−1, 1, 0)

x3(0, 0, −1)x1
x2

H-representation:
1 − x11

1 + x1
1+ x3 ≥ 0− x 2 + x3 ≥ 0+ x3 ≥ 0+ x 2 + x3 ≥ 0− x3 ≥ 0

V-representation:
v1 = (−1, 1, 0), v2 = (−1, −1, 0), v3 = (1, −1, 0),v4 = (1,1, 0), v5 = (0, 0, −1)

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedronOutline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedron• H-representation (Half-spaces): {x ∈ R n : Ax ≤ b}

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedron• H-representation (Half-spaces): {x ∈ R n : Ax ≤ b}
• V-representation (Vertices): v1 , v2 , ..., vN are the vertices of P

x

=

N
X

λi vi

i=1

where

N
X
i=1

λi

= 1,

λi ≥ 0, i = 1, 2, ..., NOutline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedron• H-representation (Half-spaces): {x ∈ R n : Ax ≤ b}
• V-representation (Vertices): v1 , v2 , ..., vN are the vertices of P

x

=

N
X

λi vi

i=1

where

N
X

λi

= 1,

λi ≥ 0, i = 1, 2, ..., N

i=1• Vertex enumeration: H-representation ⇒ V-representation

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedron• H-representation (Half-spaces): {x ∈ R n : Ax ≤ b}
• V-representation (Vertices): v1 , v2 , ..., vN are the vertices of P

x

=

N
X

λi vi

i=1

where

N
X

λi

= 1,

λi ≥ 0, i = 1, 2, ..., N

i=1• Vertex enumeration: H-representation ⇒ V-representation• Convex hull problem: V-representation ⇒ H-representation

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchTwo representations of a bounded polyhedron• H-representation (Half-spaces): {x ∈ R n : Ax ≤ b}
• V-representation (Vertices): v1 , v2 , ..., vN are the vertices of P

x

=

N
X

λi vi

i=1

where

N
X

λi

= 1,

λi ≥ 0, i = 1, 2, ..., N

i=1• Vertex enumeration: H-representation ⇒ V-representation• Convex hull problem: V-representation ⇒ H-representation• Solution methods: double description(cdd) and reverse

search(lrs)Outline

Vertex Enumeration

Reverse Search

Who uses vertex enumeration?

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...
• ...who are not experts in polyhedral computation ...

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...
• ...who are not experts in polyhedral computation ...
• ... and not software engineers

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...
• ...who are not experts in polyhedral computation ...
• ... and not software engineers• Software should be easy to install, run on standard work

stations and ...

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...
• ...who are not experts in polyhedral computation ...
• ... and not software engineers• Software should be easy to install, run on standard work

stations and ...
• ... should run faster on better hardware!

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Who uses vertex enumeration?

• Wide variety of users: scientists, engineers, economists,

operations researchers ...
• ...who are not experts in polyhedral computation ...
• ... and not software engineers• Software should be easy to install, run on standard work

stations and ...
• ... should run faster on better hardware!
• Goal: parallelize lrs for multicore workstations using existingcodeOutline

Vertex Enumeration

Reverse Search

Case study: MIT problem

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Case study: MIT problem

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Case study: MIT problem

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions• Output consists of 4862 vertices

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions• Output consists of 4862 vertices• In 1993 it took about 3 weeks to solve by cdd and 6 weeks bylrs (20MHz?)Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions• Output consists of 4862 vertices• In 1993 it took about 3 weeks to solve by cdd and 6 weeks bylrs (20MHz?)• Goal: Goal: parallelize lrs for multicore workstations using
existing codeOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions• Output consists of 4862 vertices• In 1993 it took about 3 weeks to solve by cdd and 6 weeks bylrs (20MHz?)• Goal: Goal: parallelize lrs for multicore workstations using
existing code
• In 2012:
cddr+ lrs
mplrs
cores=8cores=16 cores=32
secs
secs secs su secs
su
secs su368
496
99 5.0 44 11.2 26 19
Table: mai64: Opteron 6272, 2.1GHz, 64 cores, speedups(su) on lrs

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Case study: MIT problem• Polytope mit defined by 729 inequalities in 8 dimensions• Output consists of 4862 vertices• In 1993 it took about 3 weeks to solve by cdd and 6 weeks bylrs (20MHz?)• Goal: Goal: parallelize lrs for multicore workstations using
existing code
• In 2012:
cddr+ lrs
mplrs
cores=8cores=16 cores=32
secs
secs secs su secs
su
secs su368
496
99 5.0 44 11.2 26 19
Table: mai64: Opteron 6272, 2.1GHz, 64 cores, speedups(su) on lrs• 32-core speedup of plrs on 1993 mplrs: about 140,000 times!

(processor=110 × 1300=software)

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse SearchMore cores

Name
c40
perm10
mit71
bv7
cp6

lrs
(mai20)
10002
1
2381
1
21920
1
9040
1
17746811

96 cores
329
.48
115
.34
686
.54
302
.49
56700
.63

128 cores
247
.48
94
.31
516
.54
229
.49
43455
.62

mplrs
secs/efficiency
160 cores 192 cores 256 cores
203
179
134
.46
.44
(.44)
85
96
64
.28
.20
(.23)
412
350
231
.54
.53
(.60)
184
158
98
.49
.47
(.57)
34457
28634
18657
.63
.63
(.72)

312 cores
129
(.37)
61
(.20)
205
(.55)
88
(.52)
15995
(.69)

Table: efficiency = speedup/number of cores (mai cluster)Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Even more cores ...

Name
c40
mit71
bv7
cp6

1 core
17755
1
36198
1
10594
1
24006481

300 cores
89
.66
147
.82
48
.73
9640
.83

mplrs
600 cores
49
.60
80
.75
27
.65
4887
.82

900 cores
43
.46
63
.64
27
.44
3278
.81

1200 cores
44
.34
49
.62
29
.30
2570
.78

Table: Tsubame2.5 at Tokyo Institute of Technology: secs/efficiency

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:• Generate all triangulations on a given point set.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:• Generate all triangulations on a given point set.
• Generate all planar spanning tress on a given set of points.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:• Generate all triangulations on a given point set.
• Generate all planar spanning tress on a given set of points.
• Generate all the cells or vertices of an arrangement of lines
planes, or hyperplanes.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:• Generate all triangulations on a given point set.
• Generate all planar spanning tress on a given set of points.
• Generate all the cells or vertices of an arrangement of lines
planes, or hyperplanes.
• Generate all vertices of a convex polyhedronOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search (A. & Fukuda, ’91)

• Space efficient technique to list unstructured discrete objects• Typical Problems:• Generate all triangulations on a given point set.
• Generate all planar spanning tress on a given set of points.
• Generate all the cells or vertices of an arrangement of lines
planes, or hyperplanes.
• Generate all vertices of a convex polyhedron• Reverse search is defined by an adjacency oracle and a local

search function

Outline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated• Define graph G = (V , E ) by:

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated• Define graph G = (V , E ) by:• For every v ∈ V i = 1, 2, .., ∆ (maximum degree)(v0
Adj(v , i) =∅where vv 0 ∈ Eotherwise

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated• Define graph G = (V , E ) by:• For every v ∈ V i = 1, 2, .., ∆ (maximum degree)(v0
Adj(v , i) =∅where vv 0 ∈ Eotherwise• For every edge vv 0 in G there is a unique i such thatv 0 = Adj(v , i).

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated• Define graph G = (V , E ) by:• For every v ∈ V i = 1, 2, .., ∆ (maximum degree)(v0
Adj(v , i) =∅where vv 0 ∈ Eotherwise• For every edge vv 0 in G there is a unique i such thatv 0 = Adj(v , i).
• ”Similar” objects are joined by an edge

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Adjacency Oracle• V are the objects to be generated• Define graph G = (V , E ) by:• For every v ∈ V i = 1, 2, .., ∆ (maximum degree)(v0
Adj(v , i) =∅where vv 0 ∈ Eotherwise• For every edge vv 0 in G there is a unique i such thatv 0 = Adj(v , i).
• ”Similar” objects are joined by an edge
• Maximum degree ∆ should be as small as possible

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:• f (v ∗ ) = v ∗Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:• f (v ∗ ) = v ∗• Iterating f on any v leads to v ∗Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:• f (v ∗ ) = v ∗• Iterating f on any v leads to v ∗• Ie. f (f (f ..(f (v ))..) = v ∗Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:• f (v ∗ ) = v ∗• Iterating f on any v leads to v ∗• Ie. f (f (f ..(f (v ))..) = v ∗• f defines a spanning tree on G rooted at v ∗Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Local Search• G = (V , E ) is the given graph• v ∗ ∈ V is a target vertex• f : V 7→ V is a local search function s.t.:• f (v ∗ ) = v ∗• Iterating f on any v leads to v ∗• Ie. f (f (f ..(f (v ))..) = v ∗• f defines a spanning tree on G rooted at v ∗• Reverse search generates this tree starting at v ∗Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Example - Problem
Problem:
Generate permutations of {1, 2, .., n}
Input:
n=4
Output:(1, 2, 3, 4) (1, 2, 4, 3) (1, 3, 2, 4) (1, 3, 4, 2) (1, 4, 2, 3) (1, 4, 3, 3)(2, 1, 3, 4) (2, 1, 4, 3) (2, 3, 1, 4) (2, 3, 4, 1) (2, 4, 1, 3) (2, 4, 3, 1)(3, 1, 2, 4) (3, 1, 4, 2) (3, 2, 1, 4) (3, 2, 4, 1) (3, 4, 1, 2) (3, 4, 2, 1)(4, 1, 2, 3) (4, 1, 3, 2) (4, 2, 1, 3) (4, 2, 3, 1) (4, 3, 1, 2) (4, 3, 2, 1)

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Example - Adjacency Oracle{π1 , π2 , ..., πn }isapermutationof {1, 2, .., n}Adj(π, i) = (π1 , π2 , ..., πi−1 , πi+1 , πi , ...πn ) for i = 1, 2, ..., n − 1.
Note: ∆ = n − 1Outline

Vertex Enumeration

Reverse Search

Example - Local Search
Let π = (π1 , π2 , ..., πn )Target: (1, 2, ..., n)f (π) = (π1 , π2 , ..., πi−1 , πi+1 , πi , ..., πn )where i is the smallest index for which πi > πi+1 .

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Example - Reverse Search Tree

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Reverse Search - Pseudocode
Algorithm 1 reverseSearch(v ∗ , ∆, Adj, f )repeatv ← v∗ j ← 0
while j < ∆ doj ←j +1
if f (Adj(v , j)) = v thenv ← Adj(v , j)forward step
print vj ←0
end ifend while
if v 6= v ∗ then(v , j) ← f (v )backtrack stepend ifuntil v = v ∗ and j = ∆Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-I

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-I• G = (V , E ) is defined by the vertices and edges of thepolytope

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-I• G = (V , E ) is defined by the vertices and edges of thepolytope• Pivoting between vertices defines the adjacency oracle

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-I• G = (V , E ) is defined by the vertices and edges of thepolytope• Pivoting between vertices defines the adjacency oracle• Simplex method gives a path from any vertex to the optimum

vertexOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-I• G = (V , E ) is defined by the vertices and edges of thepolytope• Pivoting between vertices defines the adjacency oracle• Simplex method gives a path from any vertex to the optimum

vertex• lrs is a C implementation available on-line

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse search for vertex enumeration-II
http://cgm.cs.mcgill.ca/ avis/C/lrs.html

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search: features for parallelization

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search: features for parallelization• Objects generated are not stored in a database: no collisions

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search: features for parallelization• Objects generated are not stored in a database: no collisions• Each vertex is reported once and may be discarded afterwards

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search: features for parallelization• Objects generated are not stored in a database: no collisions• Each vertex is reported once and may be discarded afterwards• Subtrees may be enumerated independently without

communication

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Reverse Search: features for parallelization• Objects generated are not stored in a database: no collisions• Each vertex is reported once and may be discarded afterwards• Subtrees may be enumerated independently without

communication• Subtree size may be estimated by Hall-Knuth estimatorOutline

Vertex Enumeration

Reverse Search

Extended Reverse Search

Extension to allow :Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth• a subtree to be enumerated from its given root

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth• a subtree to be enumerated from its given root
• Additional parameters:

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth• a subtree to be enumerated from its given root
• Additional parameters:• maxd is the depth at which forward steps are terminated.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth• a subtree to be enumerated from its given root
• Additional parameters:• maxd is the depth at which forward steps are terminated.
• mind is the depth at which backtrack steps are terminated.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Extended Reverse Search

Extension to allow :• all subtrees to be listed at some fixed depth• a subtree to be enumerated from its given root
• Additional parameters:• maxd is the depth at which forward steps are terminated.
• mind is the depth at which backtrack steps are terminated.
• d is the depth of subtree root v ∗ .

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Extended Reverse Search - Pseudocode
Algorithm 2 extendedReverseSearch(v ∗ , ∆, Adj, f , d, maxd, mind)
repeatv ← v∗ j ← 0
while j < ∆ and d < maxd doj ←j +1
if f (Adj(v , j)) = v thenv ← Adj(v , j)forward step
print vj ←0d ←d +1
end ifend while
if v 6= v ∗ then(v , j) ← f (v )backtrack stepd ←d −1
end ifuntil (d = mind or v = v ∗ ) and j = ∆Outline

Vertex Enumeration

Reverse Search

Parallelization design parameters

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallelization design parameters• Users are from many disciplines and are not software

engineers!

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Parallelization design parameters• Users are from many disciplines and are not software

engineers!
• No special setup, extra library installation, or change of usage

for users

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Parallelization design parameters• Users are from many disciplines and are not software

engineers!
• No special setup, extra library installation, or change of usage

for users• Use available cores on user machine ’automatically’Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Parallelization design parameters• Users are from many disciplines and are not software

engineers!
• No special setup, extra library installation, or change of usage

for users• Use available cores on user machine ’automatically’• Reuse existing lrs code (8,000+ lines!)

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Naive Parallel Reverse Search: 3 phases• Phase 1: (single processor)• Generate the reverse search tree T down to a fixed depth
init depth.
• Redirect output nodes and store in list L.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Naive Parallel Reverse Search: 3 phases• Phase 1: (single processor)• Generate the reverse search tree T down to a fixed depth
init depth.
• Redirect output nodes and store in list L.
• Phase 2: (full parallelization)• Schedule threads from L using subtree enumeration feature.
• Use parameter max threads to limit number of parallel threads.
• Direct output to shared output stream.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Naive Parallel Reverse Search: 3 phases• Phase 1: (single processor)• Generate the reverse search tree T down to a fixed depth
init depth.
• Redirect output nodes and store in list L.
• Phase 2: (full parallelization)• Schedule threads from L using subtree enumeration feature.
• Use parameter max threads to limit number of parallel threads.
• Direct output to shared output stream.
• Phase 3: (partial parallelization)• Wait until all children threads terminate.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Search - Pseudocode
Algorithm 3 parallelReverseSearch(v ∗ , ∆, Adj, f , id, mt)
num threads ← 0
redirect output to a list L
Phase 1extendedReverseSearch(v ∗ , ∆, Adj, f , 0, id, 0)
remove all v ∈ L with depth(v ) < id and output v
while L 6= ∅ do
if num threads < mt thenremove any v ∈ L
Phase 2
num threads ← num threads + 1
extendedReverseSearch(v , ∆, Adj, f , depth(v ), ∞, depth(v ))end ifend while
while num threads > 0 do
wait for termination signal
if L 6= ∅ thenwait until a termination signal is received
extendedReverseSearch(v , ∆, Adj, f , depth(v ), ∞, depth(v ))else
num threads ← num threads − 1
Phase 3end ifend while

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Searchplrs (Implemented by Gary Roumanis)
A portable parallel implementation of lrs derived from the parallel
reverse search algorithm.
Architecture:• Light C++ wrapper around lrs.
• Leverage lrs’s restart feature.
• Use portable g++ compiler.

• Multi-producer and single consumer.
• Producer threads traverse subtrees of the reverse search tree,
appending nodes to a lock-free queue.
• Consumer thread removes nodes from shared queue andconcatenates to unified location.
• Leverage open source Boost library for atomic features.
• Ensures portability, maintainability and strong performance.

Outline

Vertex Enumeration

Reverse Search

3 Phases: CPU utilization

Figure: Input file: mit, id = 6, cores=12

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Estimates at depth 2: mit

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Search

Initial depth variation: mit

Figure: id = 3, L = 127, 124 secs

Figure: id = 4, L = 284, 105 secs

Figure: id = 6, L = 1213, 105 secs

Figure: id = 10, L = 7985, 125 secs

Outline

Vertex Enumeration

Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.
• This leads to the following issues:

Parallel Reverse SearchOutline

Vertex Enumeration

Reverse Search

Parallel Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.
• This leads to the following issues:• Success depends on balance of the reverse search tree.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.
• This leads to the following issues:• Success depends on balance of the reverse search tree.
• Conflicting issues in setting init depth.

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.
• This leads to the following issues:• Success depends on balance of the reverse search tree.
• Conflicting issues in setting init depth.
• These problems were solved in mplrs

Outline

Vertex Enumeration

Reverse Search

Parallel Reverse Searchplrs: limitations• Algorithm analysis:• No parallelization in Phase 1.
• Complete parallelizatin in Phase 2.
• Parallelization drops monotonically in Phase 3.
• This leads to the following issues:• Success depends on balance of the reverse search tree.
• Conflicting issues in setting init depth.
• These problems were solved in mplrs• Please come back for part 2!