Orthogonal Latin Squares
Download
Report
Transcript Orthogonal Latin Squares
Case study 3: orthogonal
Latin squares
Modelled by Barbara Smith
Modelling decisions
Many different ways to model even simple
problems
Combining models can be effective
Channel between models
Need additional constraints
Symmetry breaking
Implied (but logically) redundant
Orthogonal Latin squares
Find a pair of Latin
squares
Every cell has a different
pair of elements
Generalized form:
Find a set of m Latin
squares
Each possible pair is
orthogonal
Orthogonal Latin squares
1234
2143
3412
4321
11
23
34
42
22
14
43
31
1234
3412
4321
2143
33
41
12
24
44
32
21
13
Two 4 by 4 Latin
squares
No pair is repeated
History of (orthogonal) Latin
squares
Introduced by Euler in 1783
Also called Graeco-Latin or Euler squares
No orthogonal Latin square of order 2
There are only 2 (non)-isomorphic Latin squares of
order 2 and they are not orthogonal
History of (orthogonal) Latin
squares
Euler conjectured in 1783 that there are no orthogonal
Latin squares of order 4n+2
Constructions exist for 4n and for 2n+1
Took till 1900 to show conjecture for n=1
Took till 1960 to show false for all n>1
6 by 6 problem also known as the 36 officer problem
“… Can a delegation of six regiments, each of which sends a
colonel, a lieutenant-colonel, a major, a captain, a lieutenant,
and a sub-lieutenant be arranged in a regular 6 by 6 array such
that no row or column duplicates a rank or a regiment?”
More background
Lam’s problem
Existence of finite projective plane of order 10
Equivalent to set of 9 mutually orthogonal Latin squares of
order 10
In 1989, this was shown not to be possible after 2000 hours
on a Cray (and some major maths)
Orthogonal Latin squares are used in experimental
design
To ensure no dependency between independent variables
A simple 0/1 model
Suitable for integer programming
Xijkl = 1 if pair (i,j) is in row k column l, 0
otherwise
Avoiding advice never to use more than 3
subscripts!
Constraints
Each row contains one number in each square
Sum_jl Xijkl = 1
Sum_il Xijkl = 1
Each col contains one number in each square
Sum_jk Xijkl = 1
Sum_ik Xijkl = 1
A simple 0/1 model
Additional constraints
Every pair of numbers occurs exactly once
Sum_kl Xijkl = 1
Every cell contains exactly one pair of numbers
Sum_ij Xijkl = 1
Is there any symmetry?
Symmetry removal
Important for solving CSPs
Orthogonal Latin square has lots of symmetry
Especially for proofs of optimality?
Permute the rows
Permute the cols
Permute the numbers 1 to n in each square
How can we eliminate such symmetry?
Symmetry removal
Fix first row
11 22 33 …
Fix first column
11
23
32
..
Eliminates all this symmetry?
What about a CSP model?
Exploit large finite domains possible in CSPs
Reduce number of variables
O(n^4) -> ?
Exploit non-binary constraints
Problem states that squares contain pairs that are
all different
All-different is a non-binary constraint our solvers
can reason with efficiently
CSP model
2 sets of variables
Skl = i if the 1st element in row k col l is i
Tkl = j if the 2nd element in row k col l is j
How do we specify all pairs are different?
All distinct (k,l), (k’,l’)
if Skl = i and Tkl = j then Sk’l’=/ i or Tk’l’ =/ j
O(n^4) loose constraints, little constraint propagation!
What can we do?
CSP model
Introduce auxiliary variables
Fewer constraints, O(n^2)
Tightens constraint graph => more propagation
Pkl = i*n + j if row k col l contains the pair i,j
Constraints
2n all-different constraints on Skl, and on Tkl
All-different constraint on Pkl
Channelling constraint to link Pkl to Skl and Tkl
CSP model v O/1 model
CSP model
3n^2 variables
Domains of size n, n and
n^2+n
O(n^2) constraints
Large and tight nonbinary constraints
0/1 model
n^4 variables
Domains of size 2
O(n^4) constraints
Loose but linear
constraints
Use IP solver!
Solving choices for CSP model
Variables to assign
Skl and Tkl, or Pkl?
Variable and value ordering
How to treat all-different constraint
GAC using Regin’s algorithm O(n^4)
AC using the binary decomposition
Good choices for the CSP model
Experience and small instances suggest:
Assign the Skl and Tkl variables
Choose variable to assign with Fail First (smallest
domain) heuristic
Break ties by alternating between Skl and Tkl
Use GAC on all-different constraints for Skl and
Tkl
Use AC on binary decomposition of large alldifferent constraint on Pkl
Performance
n
4
0-1 model
CSP model
Fails t/sec AC
Fails t/sec
4
0.11 2
0.18
CSP model
GAC
Fails t/sec
2
0.38
5
1950
4.05 295
6
?
?
7*
20083 59.8 91687 51.1 57495 66.1
1.39 190
1.55
640235 657 442059 773
Dual CSP model
4 subscripts in 0/1 model are interchangeable
Suggests a dual model
DSij = k if the pair (i,j) occurs in row k
DTij = l if the pair (i,j) occurs in the row l
DPij = k*n + l if the pair (i,j) occurs in row i col j
Dual constraints to the primal model
Combined model
Primal and dual model together
But new search decisions
Channelling constraints to link them
Do we assign both primal and dual variables?
How do handle dual constraints (AC, GAC …)?
…
Other dualities
Any choice of 2 subscripts from 4
Diminishing returns
Dual performance
N
Primal
Fails t/sec
4
2
Dual
all vars
Fails t/sec
0.38 0
0.29
Dual
primal vars
Fails t/sec
0
0.046
5
190
1.55 94
6
442059 773 33868
146 26936 78.5
7*
57495 66.1 978
3.8 1529
0.37 67
0.34
5.5
Conclusions
Many ways to model even simple problems
Introduce auxiliary variables
Combining models often beneficial
Reduce number of constraints, improve
propagation
Channelling constraints link models
Need to deal with symmetry
Don’t always use GAC on all-different
constraints
General methodology?
Choose a basic model
Consider auxiliary variables
Consider combined models
To reduce number of
constraints, improve
propagation
Channel between views
Break symmetries
Add implied constraints
To improve propagation
Case study 4: template
design
Again model due to Barbara Smith
Introduction
Prob002 at www.csplib.org
Problem comes from a printing firm
Cat food labels that need to be printed using
templates
Several designs (tuna, chicken, …) go on each
template
Different demand for each flavour
Aside: where did cats get the taste for tuna?
Template design problem
For Francesca’s benefit
How else can I get a cat
picture into my talk?
Basic CSP model
Assume number of templates is fixed
Variables
Pij = number of slots on template i for design j
Ri = run length for template i
Constraints
Sum_j Pij = s, number of slots on each template
Sum_i Pij * Ri >= dj, total production equals
demand
Basic CSP model
Optimization problem
Introduce variable to minimize
Production = Sum_i Ri
Solved as sequence of decision problems
Production < l1, Production < l2 …
l1 set to minimum number of printings with 1 template
Symmetry
Does the model have any symmetry?
If so, how can we eliminate it?
Symmetry
The templates are indistinguishable and can be
permuted
Swap all designs on one template with all those on
a second template
Break this symmetry by distinguishing the
templates
R1 <= R2 <= R3 …
Symmetry
Designs j, k with the same demand are
indistinguishable
We can break this symmetry
[P1j,P2j,P3j,…] <lex [P1k,P2k,P3k,…]
Efficient GAC algorithm for lex ordering
constraint
Sort of symmetry?
Symmetries can be subtle to spot!
Consider designs j and j’ with demand for j
less than for j’
Suppose we produce more of j than j’
We could swap j and j’ and still have solution
Prevent this with constraint on production
Sum_i Pij Ri <= Sum_i Pij’ Ri
Implied constraints
We should always look for implied constraints
we can add to model
Encourage constraint propagation
Implied constraints
2 templates
R1+R2 = Production
R1 <= R2
Hence
R1 <= Production/2
R2 >= Production/2
Implied constraints
3 templates
R1 + R2 + R3 = Production
R1 <= R2 <= R3
Hence
R1 <= Production/3
R2 <= Production/2
R3 >= Production/3
…
Solving choices
Variable ordering
As with Golomb ruler, assign variables to
construct solution systematically
Assign all designs on one template before moving
on to a second template
Encourages constraint propagation on runlength
constraints
Performance
Basic model
Difficult to solve 2 or 3 template problems
Full model
Problem solved quickly
Can solve much larger problems than feasible with
the basic model
Optimality can still be tough!
Conclusions
Basic model often obvious
To refine such a model we need:
Consider dual/combined models
Symmetries eliminated
Implied constraints
Variable ordering heuristics
Hopefully you can start to see patterns in what
we do!