**Alphametics** are a type of mathematical puzzle. Given a
set of words, written down as a long-hand addition, find the
mapping between letters and digits. For example:

`SEND MORE ----- MONEY`

corresponds to the addition:

`9567 1085 ----- 10652`

This problem can be written as a MIP problem. As you will see, we have to take several hurdles before a final formulation is achieved that is reliable and can solve larger instances. A number of (not very well-known) modeling tricks is used.

Of course we see immediately that we can reveal the digits by solving the equation:

*1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e = 10000*m + 1000*o + 100*n + 10*e + y (*)*

where the variables *s,e,n,d,m,o,r,y* are integer
variables between 0 and 9. If we pass on just this equation to a
MIP solver, it will most likely return the solution: *s=e=n=d=m=o=r=y=0*,
which is not what we want. We need to impose a few extra
conditions: all letters map to a unique digit, and leading
letters (*s, m)* cannot be 0.

The last condition is rather easy. Let *y(i)* be the
value of letter *i*. Then include the bounds:

*y.lo('s') = 1;*

y.lo('m') = 1;

in the model. In fact, we expect this makes the model easier to solve.

The uniqueness condition (*y(i) <> y(j) for
i<>j)* is rather difficult to model. In the puzzle above
we only have 8 letters, but for our formulation we need 10
letters so we can map them into 10 digits (0..9). This can be
accomplished by just introducing two dummy letters which are not
used in the equation (*). After adding binary variables *x(i,j),
*the following constraints make sure every *y(i) *assumes
a unique number between 0 and 9:

1'x = 1'

x1 = 1

x(i,j) binary

v(j) = ord(j)-1

The *v(j)'s* are constants (with values 0,..,9) and the
variables *y(i)* can now be declared as continuous variables
as they assume only integer values automatically. Notice that the
number of binary variables is 100 no matter how large or
complicated the alphametic becomes. This number only changes if
we go from radix 10 to another base.

The objective function is just a dummy one, as the only thing we want to do is to find a feasible solution. An interesting excercise is to check whether or not an alphametic has a unique solution. This can be verified by finding a solution and then excluding this solution using a cut.

When I entered the equation (*) I felt rather uneasy as the coefficients become rather large when the problem size increases. Also the range of the magnitudes becomes very large: e.g. 1 vs. 1.0e9 for problems with words of 9 letters. This may cause numerical problems, and indeed we got slightly wrong answers for some problems. One way of attacking this problem is to do the addition slice by slice and keeping track of the carry ourselves. In our examples this would boil down to:

d+e=y+10*carry(1) carry(1)+n+r=e+10*carry(2) carry(2)+e+o=n+10*carry(3) carry(3)+s+m=o+10*carry(4) carry(4)=m

In GAMS notation this is rather simple when we use lags:

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

Note: `carry(k-1)` vanishes for the first equation.
Carry is declared as a general integer variable. As dummy
objective I chose to minimize the sum of the carries.

In order to stop the search after the first integer solution we could use an objective that does not include a variable that occurs in any other equation, e.g. by saying:

obj.. z=e=0.0;

Instead of this we used a very large *optcr*:

option optcr=100;

The alphametic we solve in the GAMS model is:

G E O R G I A O R E G O N V E R M O N T ---------------- V I R G I N I A

Another nice one is:

S A T U R N U R A N U S N E P T U N E P L U T O ------------- P L A N E T S