latin.gms : The Orthogonal Latin-Square Problem

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.

Reference

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

Large Model of Type : MIP


Category : GAMS Model library


Main file : latin.gms

$title The Orthogonal Latin-Square Problem (LATIN,SEQ=159)
$eolcom !
$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.

$Offtext

sets k  rows    / row-1*row-4/      ! change row-4 to new size
     l  columns / col-1*col-4/      ! change col-4 to new size
     v  values  / val-1*val-4/      ! change val-4 to new size

alias (i,j,v);

*  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('val-1','val-2','row-2',col-3') = 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('val-1','val-1','row-1','col-1') = 1;
*
*  and get a feasible solution. Both the original and a new formulation
*  are given.

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

equations
   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('val-1','val-1','row-1','col-1') = 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 /

variables  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;

equations

   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','val-1','row-1','col-1') = 1;

solve newlatin min w us 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;