In http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz we find the huge alphametic (I like the term cryptarithm mentioned as alternative even better):

A N A C C E L E R A T I N G I N F E R E N T I A L E N G I N E E R I N G T A L E E L I T E G R A N T F E E E T C E T E R A A R T I F I C I A L I N T E L L I G E N C E

The simple formulation from this posting leads to problems even for Cplex. The stable formulation from this posting is a winner here: it yields a quick solution that is correct.

### Simple formulation

`$ontext`

Alphametics, Simple formulation

This does not work very well.

Erwin Kalvelagen

AN

+ ACCELERATING

+ INFERENTIAL

+ ENGINEERING

+ TALE

+ ELITE

+ GRANT

+ FEE

+ ET

+ CETERA =

-------------

ARTIFICIAL

+ INTELLIGENCE

$offtext

set i /A,N,C,E,L,R,T,I,G,F/;

alias (i,j);

set leading(i) /A,I,E,T,G,F,C/;

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

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

variables

y(i) 'decision variables'

x(i,j) 'auxiliary variables for uniqueness'

z 'dummy objective variable'

;

binary variable x;

equation

addition 'the actual problem'

ydef(i) 'calculate y'

xrow(i) 'row sums'

xcol(j) 'column sums'

dummy_objective

;

addition..

10*y('A')+y('N')+

1e11*y('A')+1e10*y('C')+1e9*y('C')+1e8*y('E')+1e7*y('L')+1e6*y('E')+1e5*y('R')+1e4*y('A')+1e3*y('T')+100*y('I')+10*y('N')+y('G')+

1e10*y('I')+1e9*y('N')+1e8*y('F')+1e7*y('E')+1e6*y('R')+1e5*y('E')+1e4*y('N')+1e3*y('T')+100*y('I')+10*y('A')+y('L')+

1e10*y('E')+1e9*y('N')+1e8*y('G')+1e7*y('I')+1e6*y('N')+1e5*y('E')+1e4*y('E')+1e3*y('R')+100*y('I')+10*y('N')+y('G')+

1e3*y('T')+100*y('A')+10*y('L')+y('E')+

1e4*y('E')+1e3*y('L')+100*y('I')+10*y('T')+y('E')+

1e4*y('G')+1e3*y('R')+100*y('A')+10*y('N')+y('T')+

100*y('F')+10*y('E')+y('E')+

10*y('E')+y('T')+

1e5*y('C')+1e4*y('E')+1e3*y('T')+100*y('E')+10*y('R')+y('A') =e=

1e9*y('A')+1e8*y('R')+1e7*y('T')+1e6*y('I')+1e5*y('F')+1e4*y('I')+1e3*y('C')+100*y('I')+10*y('A')+y('L')+

1e11*y('I')+1e10*y('N')+1e9*y('T')+1e8*y('E')+1e7*y('L')+1e6*y('L')+1e5*y('I')+1e4*y('G')+1e3*y('E')+100*y('N')+10*y('C')+y('E');

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(leading) = 1;

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

model m /all/;

m.optfile=1;

solve m using mip minimizing z;

option y:0;

display y.l;

The numbers in the addition equation are really become too big for comfort. It is surprising that some solvers such as Gurobi can deliver a good solution for this model, but as expected some others can not. The poor scaling can create severe havoc. The model can be downloaded from here.

### Stable formulation

`$ontext`

Alphametics, stable formulation

AN

+ ACCELERATING

+ INFERENTIAL

+ ENGINEERING

+ TALE

+ ELITE

+ GRANT

+ FEE

+ ET

+ CETERA =

-------------

ARTIFICIAL

+ INTELLIGENCE

Erwin Kalvelagen, 2009

$offtext

set

i 'letters' /A,N,C,E,L,R,T,I,G,F/

w 'words' /an,accelerating,inferential,engineering,tale,elite,grant,fee,et,cetera,

artificial,intelligence/

w1(w) /an,accelerating,inferential,engineering,tale,elite,grant,fee,et,cetera/

w2(w) /artificial,intelligence/

;

alias (i,j);

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

set

k 'slices (slice1 if rightmost slice)' /slice1*slice12/

lead(i) 'leading letters' /A,I,E,T,G,F,C/

;

set letters(w,i,k) /

an.(a.slice2, n.slice1)

accelerating.(a.slice12, c.slice11, c.slice10, e.slice9, l.slice8, e.slice7,

r.slice6, a.slice5, t.slice4, i.slice3, n.slice2, g.slice1)

inferential.(i.slice11, n.slice10, f.slice9, e.slice8, r.slice7, e.slice6,

n.slice5, t.slice4, i.slice3, a.slice2, l.slice1)

engineering.(e.slice11, n.slice10, g.slice9, i.slice8, n.slice7, e.slice6,

e.slice5, r.slice4, i.slice3, n.slice2, g.slice1)

tale.(t.slice4, a.slice3, l.slice2, e.slice1)

elite.(e.slice5, l.slice4, i.slice3, t.slice2, e.slice1)

grant.(g.slice5, r.slice4, a.slice3, n.slice2, t.slice1)

fee.(f.slice3, e.slice2, e.slice1)

et.(e.slice2, t.slice1)

cetera.(c.slice6, e.slice5, t.slice4, e.slice3, r.slice2, a.slice1)

artificial.(a.slice10, r.slice9, t.slice8, i.slice7,

f.slice6, i.slice5, c.slice4, i.slice3, a.slice2, l.slice1)

intelligence.(i.slice12, n.slice11, t.slice10, e.slice9, l.slice8, l.slice7,

i.slice6, g.slice5, e.slice4, n.slice3, c.slice2, e.slice1)

/;

parameter lhs(k,i), rhs(k,i);

lhs(k,i) = sum(letters(w1,i,k),1);

rhs(k,i) = sum(letters(w2,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('slice12')=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;

The solution I get is:

---- 106 VARIABLE y.L decision variables

A 5, N 9, C 7, E 4, R 2, T 1, I 6, G 8, F 3

where y(‘L’)=0 is implied. This formulation is stable: it yields correct solutions for all MIP solvers. The model can be downloaded here.

## No comments:

## Post a Comment