Description

A latin square is an arrangement of objects such that no object
is repeated in a row or column. Two latin squares are orthogonal
if all entries are different. For example,

        one     two
       1 3 2   2 1 3
       3 2 1   1 3 2
       2 1 3   3 2 1

The case of n = 10 has historical interest and was only settled in 1952.

The original formulation is not correct. A new formulation
is presented which generates a correct solution. Also note that the
solution time is very sensitive to formulation details and depends on
the kind of algorithm used.

The size of the square can easily by changed by editing the lines
containing the definitions of the rows, columns and values in the.
set definition below. This kind of assignment problem can be very
difficult to solve for general purpose MIP codes.

Large Model of Type : MIP

Category : GAMS Model library

Main file : latin.gms

$title The Orthogonal Latin-Square Problem (LATIN,SEQ=159)

$onText
A latin square is an arrangement of objects such that no object
is repeated in a row or column. Two latin squares are orthogonal
if all entries are different. For example,

        one     two
       1 3 2   2 1 3
       3 2 1   1 3 2
       2 1 3   3 2 1

The case of n = 10 has historical interest and was only settled in 1952.

The original formulation is not correct. A new formulation
is presented which generates a correct solution. Also note that the
solution time is very sensitive to formulation details and depends on
the kind of algorithm used.

The size of the square can easily by changed by editing the lines
containing the definitions of the rows, columns and values in the.
set definition below. This kind of assignment problem can be very
difficult to solve for general purpose MIP codes.


Dantzig, G B, Chapter 26.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Keywords: mixed integer linaer programming, latin square, mathematics
$offText

$eolCom //

$if not set SIZE $set SIZE 4  // set --SIZE=n on GAMS command line to new size n

Set
   k 'rows'    / row1*row%SIZE% /
   l 'columns' / col1*col%SIZE% /
   v 'values'  / val1*val%SIZE% /;

Alias (i,j,v);

$onText ORIGINAL FORMULATION
Note that the squares use k,l for row and column indexes. The first
index position (i) is for the values of square one and the second
index position (j) is for square two. For example, the cell 2,3
in the latin square shown above would be defined by the value of
one for the following index values:

    x.fx('val1','val2','row2',col3') = 1;

The original formulation is not correct. For example, you can pick
any cell (k,l) and pick and make the cell values equal and the
model will find a feasible solution. For example, you could set:

    x.fx('val1','val1','row1','col1') = 1;

and get a feasible solution. Both the original and a new formulation
are given.
$offText

Variable
   x(i,j,k,l) 'pairs (i,j) allocated to cell(k,l)'
   z          'some objective';

Binary Variable x;

Equation
   c1(i,j) 'for each cell pick only one item pair'
   c2(k,l) 'an item pair can show up only once'
   c3(i,l) 'items have to be unique in each column for square one'
   c4(j,l) 'items have to be unique in each column for square two'
   c5(i,k) 'items have to be unique in each row for square one'
   c6(j,k) 'items have to be unique in each row for square two'
   obj     'some objective function';

c1(i,j)..   sum((k,l), x(i,j,k,l)) =e= 1;

c2(k,l)..   sum((i,j), x(i,j,k,l)) =e= 1;

c3(i,l)..   sum((j,k), x(i,j,k,l)) =e= 1;

c4(j,l)..   sum((i,k), x(i,j,k,l)) =e= 1;

c5(i,k)..   sum((j,l), x(i,j,k,l)) =e= 1;

c6(j,k)..   sum((i,l), x(i,j,k,l)) =e= 1;

obj.. z =e= sum((i,j,k,l), x(i,j,k,l));

Model latin / all /;

Parameter report(*,k,l);

option report:0:1:1;

$onText skip over old model
* force an incorrect solution
x.fx('val1','val1','row1','col1') = 1;

solve latin minimizing z using mip;

loop((i,j,k,l)$x.l(i,j,k,l),
   report('one',k,l) = ord(i);
   report('two',k,l) = ord(j);
);
display report;
$offText

* New Formulation
Set s 'square' / one, two /;

Variable
   y(s,v,k,l) 'square s has value v in cell(k,l)'
   dev(v,k,l) 'deviation from correct formulation'
   w          'some objective';

Binary Variable y;

Equation
   n2(s,k,l) 'exactly one value for each cell'
   n3(s,v,l) 'columns entries have to be unique'
   n5(s,v,k) 'row entries have to be unique'
   n6(v,k,l) 'entries in squares have to be different'
   nobj      'definition of objective - anything';

n2(s,k,l)..  sum(v, y(s,v,k,l)) =e= 1;

n3(s,v,l)..  sum(k, y(s,v,k,l)) =e= 1;

n5(s,v,k)..  sum(l, y(s,v,k,l)) =e= 1;

n6(v,k,l)..  sum(s, y(s,v,k,l)) =l= 1;

nobj.. w =e= sum((s,v,k,l), y(s,v,k,l));

Model newlatin / nobj, n2, n3, n5, n6 /;

* position the solution
y.fx('one','val1','row1','col1') = 1;

solve newlatin min w using mip;

loop((s,v,k,l)$y.l(s,v,k,l),
   report(s,k,l) = ord(v);
   report(s,k,l) = ord(v);
);
display report;