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:
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:
Instead of this we used a very large optcr:
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