Alphametics (2)

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

In this posting we developed an equation

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:

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.