Saturday, April 25, 2009

Alphametics (2)

The problem we are trying to solve is the alphametic puzzle:

alphametic3

In this posting we developed an equation

alphameticeq

that caused some problems.

A different formulation can be developed that circumvents this problem. We can use the addition algorithm taught to us in primary school: first add the right most digits, and save a possible carry. Then add up the digits in the second rightmost column, including the previous carry, etc. This scheme can actually be implemented in constraints as follows:

alphameticeq2

The complete model can look like:

$ontext

  Alphametics, stable formulation

     G E O R G I A        8 4 6 5 8 0 2
       O R E G O N   ->     6 5 4 8 6 3
     V E R M O N T        1 4 5 9 6 3 7
     -------------      ---------------
   V I R G I N I A      1 0 5 8 0 3 0 2

   Erwin Kalvelagen, 1998, updated 2009

$offtext

set
   i 'letters' /g,e,o,r,i,a,n,v,m,t/
   w 'words'   /georgia, oregon, vermont, virginia/
   wadd(w)     /georgia, oregon, vermont /
;

alias (i,j);
abort$(card(i) <> 10) "set i should have 10 elements";

set
  k 'slices (slice1 if rightmost slice)' /slice1*slice8/
  lead(i) 'leading letters' /g,o,v/
;

set letters(w,i,k) /
georgia.(
    g.slice7
    e.slice6
    o.slice5
    r.slice4
    g.slice3
    i.slice2
    a.slice1
   )
oregon.(
    o.slice6
    r.slice5
    e.slice4
    g.slice3
    o.slice2
    n.slice1
)
vermont.(
    v.slice7
    e.slice6
    r.slice5
    m.slice4
    o.slice3
    n.slice2
    t.slice1
)
virginia.(
    v.slice8
    i.slice7
    r.slice6
    g.slice5
    i.slice4
    n.slice3
    i.slice2
    a.slice1
)
/;

parameter lhs(k,i), rhs(k,i);
lhs(k,i) = sum(letters(wadd,i,k),1);
rhs(k,i) = sum(letters('virginia',i,k),1);

parameter v(i); v(i) = ord(i)-1;

variables
  y(i)     'decision variables'
  x(i,j)   'auxiliary variables for uniqueness'
  carry(k)
  z        'dummy objective variable'
;
binary variable x;
integer variable carry;

equation
  addition(k)  'the actual problem'
  ydef(i)      'calculate y'
  xrow(i)      'row sums'
  xcol(j)      'column sums'
  dummy_objective

;

addition(k)..
   carry(k-1) + sum(i, lhs(k,i)*y(i)) =e=
       sum(i, rhs(k,i)*y(i)) + 10*carry(k);

carry.fx('slice8')=0;

ydef(i).. y(i) =e= sum(j, x(i,j)*v(j));
xrow(i).. sum(j, x(i,j)) =e= 1;
xcol(j).. sum(i, x(i,j)) =e= 1;

*
* bounds on leading digits: they can not be 0
*
y.lo(lead) = 1;

dummy_objective.. z =e= sum(i, y(i));

model m /all/;
solve m using mip minimizing z;
option y:0;
display y.l;

This model solves without a problem even with the GAMS version of GLPK:

**** SOLVER STATUS     1 NORMAL COMPLETION        
**** MODEL STATUS      8 INTEGER SOLUTION         
**** OBJECTIVE VALUE               45.0000

----    113 VARIABLE y.L  decision variables

g 8,    e 4,    o 6,    r 5,    a 2,    n 3,    v 1,    m 9,    t 7

The only small bug here is that this solution is actually optimal, so the model status is reported incorrectly.