Transcript padova6 - School of Computing Science

Case study 7:
Langford’s problem
Model due to Barbara Smith
Outline
 Introduction

Langford’s problem
 Modelling


it as a CSP
Basic model
Refined model
 Experimental
 Conclusions
Results
Recipe

Create a basic model


Decide on the variables
Introduce auxiliary variables

For messy/loose constraints

Consider dual, combined or
0/1 models
 Break symmetry
 Add implied constraints
 Customize solver

Variable, value ordering
Langford’s problem

Prob024 @
www.csplib.org
 Find a sequence of 8
numbers



Each number [1,4]
occurs twice
Two occurrences of i
are i numbers apart
Unique solution

41312432
Langford’s problem

L(k,n) problem




To find a sequence of k*n
numbers [1,n]
Each of the k successive
occrrences of i are i apart
We just saw L(2,4)
Due to the mathematician
Dudley Langford

Watched his son build a
tower which solved L(2,3)
Langford’s problem

L(2,3) and L(2,4) have unique solutions
 L(2,4n) and L(2,4n-1) have solutions



L(2,4n-2) and L(2,4n-3) do not
Computing all solutions of L(2,19) took 2.5 years!
L(3,n)


No solutions: 0<n<8, 10<n<17, 20, ..
Solutions:
9,10,17,18,19, ..
A014552
Sequence:
0,0,1,1,0,0,26,150,0,0,17792,108144,0,0,39809640,326721800,
0,0,256814891280,2636337861200
Basic model
 What
are the variables?
Basic model
 What
are the variables?
Variable for each occurrence of a number
X11 is 1st occurrence of 1
X21 is 1st occurrence of 2
..
X12 is 2nd occurrence of 1
X22 is 2nd occurrence of 2
..
 Value
is position in the sequence
Basic model
 What



are the constraints?
Xij in [1,n*k]
Xij+1 = i+Xij
Alldifferent([X11,..Xn1,X12,..Xn2,..,X1k,..Xnk])
Recipe

Create a basic model


Decide on the variables
Introduce auxiliary variables

For messy/loose constraints

Consider dual, combined or
0/1 models
 Break symmetry
 Add implied constraints
 Customize solver

Variable, value ordering
Break symmetry
 Does
the problem have any symmetry?
Break symmetry
 Does

the problem have any symmetry?
Of course, we can invert any sequence!
Break symmetry
 How
do we break this symmetry?
Break symmetry
 How


do we break this symmetry?
Many possible ways
For example, for L(3,9)
• Either X92 < 14 (2nd occurrence of 9 is in 1st half)
• Or X92=14 and X82<14 (2nd occurrence of 8 is in
1st half)
Recipe

Create a basic model


Decide on the variables
Introduce auxiliary variables

For messy/loose constraints

Consider dual, combined or
0/1 models
 Break symmetry
 Add implied constraints
 Customize solver

Variable, value ordering
What about dual model?
 Can
we take a dual view?
What about dual model?
 Can
we take a dual view?
 Of course we can, it’s a permutation!
Dual model
 What

are the variables?
Variable for each position i
 What
are the values?
Dual model
 What

Variable for each position i
 What


are the variables?
are the values?
If use the number at that position, we cannot
use an all-different constraint
Each number occurs not once but k times
Dual model
 What

Variable for each position i
 What


are the variables?
are the values?
Solution 1: use values from [1,n*k] with the
value i*n+j standing for the ith occurrence of j
Now want to find a permutation of these
numbers subject to the distance constraint
Dual model

What are the variables?


Variable for each position i
What are the values?



Solution 2: use as values the numbers [1,n]
Each number occurs exactly k times
Fortunately, there is a generalization of all-different
called the global cardinality constraint (gcc) for this
Global cardinality constraint
 Gcc([X1,..Xn],l,u)
enforces values used by
Xi to occur between l and u times

All-different([X1,..Xn]) = Gcc([X1,..Xn],1,1)
 Regin’s
algorithm enforces GAC on Gcc in
O(n^2.d)

Regin’s papers are tough to follow but this
seems to beat his algorithm for all-different!?
Dual model
 What


are the constraints?
Gcc([D1,…Dk*n],k,k)
Distance constraints?
Dual model
 What


are the constraints?
Gcc([D1,…Dk*n],k,k)
Distance constraints:
• Di=j then Di+j+1=j
Combined model
 Primal
and dual variables
 Channelling to link them

What do the channelling constraints look like?
Combined model
 Primal
and dual variables
 Channelling to link them

Xij=k implies Dk=i
Solving choices?
 Which

variables to assign?
Xij or Di
Solving choices?
 Which

Xij or Di, doesn’t seem to matter
 Which

variables to assign?
variable ordering heuristic?
Fail First or Lex?
Solving choices?
 Which

Xij or Di, doesn’t seem to matter
 Which

variables to assign?
variable ordering heuristic?
Fail First very marginally better than Lex
 How
to deal with the permutation
constraint?



GAC on the all-different
AC on the channelling
AC on the decomposition
Solving choices?
 Which

Xij or Di, doesn’t seem to matter
 Which

variables to assign?
variable ordering heuristic?
Fail First very marginally better than Lex
 How
to deal with the permutation
constraint?

AC on the channelling is often best for time
Conclusions

Modelling is an art but there are patterns

Develop basic model
• Decide on the variables and their values





Use auxiliary variables to represent constraints
compactly/efficiently
Consider dual, combined and 0/1 models
Break symmetry
Add implied constraints
Customize solver for your model
Case study 8: social
golfers problem
Model again due to Barbara Smith
Outline
 Introduction

Social golfers problem
 Modelling


it as a CSP
Basic model
Refined model
 Experimental
 Conclusions
Results
Social golfers problem

Prob013 @
www.csplib.org
 32 golfers wish to
play in 8 groups of 4
each week


No two play in the
same group more than
once
How many weeks can
they play?
Social golfers problem

Prob013 @
www.csplib.org
 32 golfers wish to
play in 8 groups of 4
each week


No two play in the
same group more than
once
How many weeks can
they play?

9 weeks and this is
optimal
Social golfers problem

Of course, generalize problem to g groups of s
players over w weeks
 Kirkman’s schoolgirls’ problem [Lady’s &
Gentleman’s Diary 1850]
“… a schoolmistress was in the habit of taking her girls
for a daily walk. The girls were 15 in number, and
were arranged in 5 rows of 3 each, so that each girl
might have 2 companions. The problem is to so
dispose them so that for 7 consecutive days no girl
will walk with any of her school-fellows in a triplet
twice …”
This is equivalent to social golfers problem of 5 groups
of 3 players over 7 weeks
Recipe

Create a basic model


Introduce auxiliary variables





Decide on the variables
For messy/loose constraints
Consider dual, combined or 0/1
models
Break symmetry
Add implied constraints
Customize solver

Variable, value ordering
Basic model
 What
are the variables?
Basic model
 What


are the variables?
Group_ij is the set of s golfers assigned to
group i in period j
But I haven’t shown you set variables before!
Set variables
 CSP
variables can range over (finite)
domains like integers

X1 is 1, 2, 3 or 4
 Or

over sets of (finite) domains
Y1 is {}, {1}, {2}, or {1,2}
Set variables
 CSP
variables can range over (finite)
domains like integers

X1 is 1, 2, 3 or 4
 Or

over sets of (finite) domains
Y1 is {}, {1}, {2}, or {1,2}
 Usually
set operations can be posted as
constraints on these set variables

Y1 subset Z1, Y1 intersect Z1 = {}, 1 in Y1, …
Set variables
 Set
variables are potentially expensive to
reason about

If X1 is a subset of Y1, then X1 has
exponentially many possible values
 Compromise


CSP solvers just maintain upper and lower
bounds on set variable
{} subseteq X1 subseteq {1,2}
Set variables
 Set
variables are potentially expensive to
reason about

If X1 is a subset of Y1, then X1 has
exponentially many possible values
 Compromise



CSP solvers just maintain upper and lower
bounds on set variable
{} subseteq X1 subseteq {1,2}
We loose the ability to represent disjunction
E.g. X1= {1} or X1={2} but X1=/ {1,2}
Basic model
 What

are the variables?
Group_ij is the set of s golfers assigned to
group i in period j
 What
are constraints?
Basic model
 What

Group_ij is the set of s golfers assigned to
group i in period j
 What



are the variables?
are constraints?
Size of group, |Group_ij|=s
Groups do not overlap, Group_ij intersect
Group_i’j={}
Never meet twice,
for j<l . | Group_ij intersect Group_kl | <= 1
Break symmetry
 What
symmetry does the problem have?
Break symmetry
 What
symmetry does the problem have?
 Lots!



Players are symmetrical
Groups are symmetrical
Weeks are symmetrical
Break symmetry
 What
symmetry does the problem have?
 Lots!



Players are symmetrical
Groups are symmetrical
Weeks are symmetrical
 Set
variables saved us worrying about
order within group
Break symmetry
 We
can assign some values and break
some of this symmetry
Break symmetry
 We
can assign some values and break
some of this symmetry

Make first week: {1,2,..s}, {s+1,s+2,..2s},…
Break symmetry
 We
can assign some values and break
some of this symmetry


Make first week: {1,2,..s}, {s+1,s+2,..2s},…
In second week: player j is in jth group
Break symmetry
 Symmetry


is still left
Weeks 2 and onwards remain symmetric
Hard to post constraints to break this
• E.g. smallest player in week k who plays in the
same group as player n is smaller than smallest
player in week k+1 who plays in the same group
as player n
Recipe

Create a basic model


Introduce auxiliary variables





Decide on the variables
For messy/loose constraints
Consider dual, combined or 0/1
models
Break symmetry
Add implied constraints
Customize solver

Variable, value ordering
Alternative model
 Focus
on pairs of players that play
together
 Less intrinsic symmetry
Alternative model
 What
are the variables?
Alternative model
 What

are the variables?
Number the pairs
<1,2> is 0
<1,3> is 1
..
<1,n> is n-2
<2,3> is n-1
..
Alternative model
 What


are the variables?
Number the pairs
Variable Week_k is the week that pair number
k meet
Alternative model
 What


are the variables?
Number the pairs
Variable Week_k is the week that pair number
k meet
• If they never meet, it is 0
Symmetry in alternative
model
 Less



symmetry
Again, no symmetry in order of players within
group
Now, no symmetry between groups in week
Indeed, groups are not explicitly named!
Constraints in alternative
model
 No

pair meets twice
Implicit in assigning single value to Week_k
 Groups


are closed
If i and j play together in week t, and j and k
play together in week t then i and k play
together
Lots of messy constraints
Recipe

Create a basic model


Introduce auxiliary variables





Decide on the variables
For messy/loose constraints
Consider dual, combined or 0/1
models
Break symmetry
Add implied constraints
Customize solver

Variable, value ordering
Introduce auxiliary variables
 Players_ik
week k
= set of players playing with i in
Introduce auxiliary variables
 Players_ik
= set of players playing with i in
week k


i belongs to Players_ik
NB still haven’t named groups
Introduce auxiliary variables
 Players_ik
= set of players playing with i in
week k

i belongs to Players_k
 Combine
with initial model
Combined model
 Express
constraints in model where they
are easiest!
 Channelling constraints to link models


Week_k=t with k=<i,j> implies
Players_it=Players_jt
Week_k/=t with k=<i,j> implies Players_it
intersect Players_jt = {}
Combined model
 Express
constraints in model where they
are easiest!
 Channelling constraints to link models



Week_k=t with k=<i,j> implies
Players_it=Players_jt
Week_k/=t with k=<i,j> implies Players_it
intersect Players_jt = {}
NB build in knowledge about transitivity
Recipe

Create a basic model


Introduce auxiliary variables





Decide on the variables
For messy/loose constraints
Consider dual, combined or 0/1
models
Break symmetry
Add implied constraints
Customize solver

Variable, value ordering
Implied constraints
 Take
a group from any week, {g1,..gs}
 In any other week, these players must be
spread over exactly s groups

Adds significant overhead but can be useful
on certain problems
Week symmetry
 Excuse
the pun (week/weak)
 We devised a model without groups

Eliminating group symmetry
 We

still have lots of week symmetry
Can we model without weeks?
Week symmetry
 Excuse
the pun (week/weak)
 We devised a model without groups

Eliminating group symmetry
 We




still have lots of week symmetry
Can we model without weeks?
Surprisingly, yes
Model is convoluted but gives good results
First model to solve Kirkman’s schoolgirls
problel
3rd Model
 What

are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
3rd Model
 What

are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
• k belongs to AllPairs_k
3rd Model
 What


are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
SameWeek_k is the set of all pairs playing in
the same week as k
3rd Model
 What



are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
SameWeek_k is the set of all pairs playing in
the same week as k
PlayersWithPair_k is the set of individual
players playing with k
3rd Model
 What



are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
SameWeek_k is the set of all pairs playing in
the same week as k
PlayersWithPair_k is the set of individual
players playing with k
• If k=<i,j> then i and j belong to PlayersWithPair_k
3rd Model
 What




are the variables?
AllPairs_k is the set of all pairs playing with
pair k (k=<i,j>)
PairsSameWeek_k is the set of all pairs
playing in the same week as k
PlayersWithPair_k is the set of individual
players playing with k
PlaySameWeek_kk’ is 1 iff k and k’ play in
same week and 0 otherwise
Channelling
 We

can channel back to the 2nd model
if Week_k=Week_k’ then
• PairsSameWeek_k = PairsSameWeek_k’

If Week_k/=Week_k’ then
• PairsSameWeek_k intersect PairsSameWeek_k’ =
{}
…
Symmetry remaining
 Players


are still symmetrical
Can assign first week
{1,2,..s},{s+1,..,2s},…
Conclusions
 Constraints
can improve your golf!
 Set variables are useful for modelling

Eliminate symmetry
 Alternatively,
we can channel into a model
with less symmetry

Even if it is cumbersome, it can help
 More
about set variables and global (nonbinary) constraints on set variables next
week