Sunday, April 26, 2009

Alphametics (4)

A CSP solver with the All-different constraint can make the modeling of alphametic problems even easier. For instance with Microsoft Solver Foundation:

Model[
   Decisions[Integers[0,9],s,e,n,d,m,o,r,y],
   Constraints[
     1e3*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e == 10000*m + 1000*o + 100*n + 10*e + y,
     Unequal[s,e,n,d,m,o,r,y],
     s>=1,m>=1]
]

This solves just fine, but now lets move to the more difficult problem:
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
I encoded this as:

Model[
  Decisions[Integers[0,9],A,N,C,E,L,R,T,I,G,F],
  Constraints[
    10*A+N+
    1e11*A+1e10*C+1e9*C+1e8*E+1e7*L+1e6*E+1e5*R+1e4*A+1e3*T+100*I+10*N+G+
    1e10*I+1e9*N+1e8*F+1e7*E+1e6*R+1e5*E+1e4*N+1e3*T+100*I+10*A+L+
    1e10*E+1e9*N+1e8*G+1e7*I+1e6*N+1e5*E+1e4*E+1e3*R+100*I+10*N+G+
    1e3*T+100*A+10*L+E+
    1e4*E+1e3*L+100*I+10*T+E+
    1e4*G+1e3*R+100*A+10*N+T+
    100*F+10*E+E+
    10*E+T+
    1e5*C+1e4*E+1e3*T+100*E+10*R+A
       ==
    1e9*A+1e8*R+1e7*T+1e6*I+1e5*F+1e4*I+1e3*C+100*I+10*A+L+
    1e11*I+1e10*N+1e9*T+1e8*E+1e7*L+1e6*L+1e5*I+1e4*G+1e3*E+100*N+10*C+E,
    A>=1, I>=1,E>=1,T>=1,G>=1,F>=1,C>=1,
    Unequal[A,N,C,E,L,R,T,I,G,F]
  ]
]

This model produces Infeasible:

alphameticcsp2

I had hopes that the rational arithmetic of MSF could help here. Of course we can apply the more stable formulation we used in the MIP formulation here.

Model[
  Decisions[Integers[0,9],A,N,C,E,L,R,T,I,G,F],
  Decisions[Integers[0,Infinity],carry1,carry2,carry3,carry4,carry5,carry6,carry7,carry8,carry9,carry10,carry11],
  Constraints[
    N + G + L + G + E + E + T + E + T + A == L + E + 10*carry1,
    A + N + A + N + L + T + N + E + E + R + carry1 == A + C + 10*carry2,
    I + I + I + A + I + A + F + E + carry2 == I + N + 10*carry3,
    T + T + R + T + L + R + T + carry3 == C + E + 10*carry4,
    A + N + E + E + G + E + carry4 == I + G + 10*carry5,
    R + E + E + C + carry5 == F + I + 10*carry6,
    E + R + N + carry6 == I + L + 10*carry7,
    L + E + I + carry7 == T + L + 10*carry8,
    E + F + G + carry8 == R + E + 10*carry9,
    C + N + N + carry9 == A + T + 10*carry10,
    C + I + E + carry10 == N + 10*carry11,
    A + carry11 == I,
    A>=1, I>=1,E>=1,T>=1,G>=1,F>=1,C>=1,
    Unequal[A,N,C,E,L,R,T,I,G,F]
  ]
]

This now solves quickly:

alphameticcsp1

So why is the simple formulation not working. It seems related to the Unequal construct. When we feed the solution into the problem we get:

  1. Infeasible if Unequal statement is part of the model.
  2. Feasible is Unequal statement is removed.

This may indicate a bug or some intricate numerics suddenly playing a role.

Model[
  Decisions[Integers[0,9],A,N,C,E,L,R,T,I,G,F],
  Constraints[
    10*A+N+
    1e11*A+1e10*C+1e9*C+1e8*E+1e7*L+1e6*E+1e5*R+1e4*A+1e3*T+100*I+10*N+G+
    1e10*I+1e9*N+1e8*F+1e7*E+1e6*R+1e5*E+1e4*N+1e3*T+100*I+10*A+L+
    1e10*E+1e9*N+1e8*G+1e7*I+1e6*N+1e5*E+1e4*E+1e3*R+100*I+10*N+G+
    1e3*T+100*A+10*L+E+
    1e4*E+1e3*L+100*I+10*T+E+
    1e4*G+1e3*R+100*A+10*N+T+
    100*F+10*E+E+
    10*E+T+
    1e5*C+1e4*E+1e3*T+100*E+10*R+A
       ==
    1e9*A+1e8*R+1e7*T+1e6*I+1e5*F+1e4*I+1e3*C+100*I+10*A+L+
    1e11*I+1e10*N+1e9*T+1e8*E+1e7*L+1e6*L+1e5*I+1e4*G+1e3*E+100*N+10*C+E,
   A>=1, I>=1,E>=1,T>=1,G>=1,F>=1,C>=1,
  //  Unequal[A,N,C,E,L,R,T,I,G,F],
    A==5,N==9,C==7,E==4,L==0,R==2,T==1,I==6,G==8,F==3
  ]
]

Actually I would have expected problems in the big equality condition and not in the Unequal constraint.

Update: I understand now the behavior a little bit more. Without the Unequal the MIP solver Gurobi is called. This produces the correct conclusion: Feasible. With the Unequal statement enabled the CSP solver is used and that solver has problems with this model. Actually Gurobi uses floating point instead of rational arithmetic. So it is somewhat surprising that Gurobi is more accurate on this model than the CSP solver.

Update2: see expert explanation in comment. CSP wants all intermediate results (I think all terms used in any expression) also to fit in an integer.