A CSP solver with the All-different constraint can make the modeling of alphametic problems even easier. For instance with Microsoft Solver Foundation:
This solves just fine, but now lets move to the more difficult problem:
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]
]
I encoded this as:
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
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:
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:
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:
- Infeasible if Unequal statement is part of the model.
- 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.
Hi Erwin,
ReplyDeleteI am sure this is caused by the CSP solver restriction on largest possible integer range (default interval): [ConstraintSystem.MinFinite, ConstraintSystem.MaxFinite], which is defined so that overflows can be caught. Since CSP solver performs integer arithmetic precisely, any calculation that will lead to an overflow of the default interval will get rejected. In the model, the single == constraint will yield values outside the range when we plug in the solution. So CSP solver will not even search that part of the search space.
The reformulation works since, with the help of decision variable carry*, we reduce the values of the arithmetic down to the default interval.
Thanks.
That makes sense. Thanks! Erwin
ReplyDelete