Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

SEND+MORE=MONEY (Milp programming)

Her is the code (unhappily wrong) for the famous verbal arithmetic : SEND+MORE=MONEY coded by Simon (Puzzle—Verbal Arithmetic and Mastermind --- accessible in line)

p = MixedIntegerLinearProgram(maximization=True,solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[0,0])
for i in range(9) :
        for j in range(8) :
            p.set_binary(v[i,j])
#S=sum(j*v[0,j] for i in range(0,7))
#E=sum(j*v[1,j] for i in range(0,7))
#N=sum(j*v[2,j] for i in range(0,7))
#D=sum(j*v[3,j] for i in range(0,7))
#M=sum(j*v[4,j] for i in range(0,7))
#O=sum(j*v[5,j] for i in range(0,7))
#R=sum(j*v[6,j] for i in range(0,7))
#Y=sum(j*v[7,j] for i in range(0,7))
# Une lettre n'est représentée que par un chiffre
for j in range(8) :
    p.add_constraint(sum(v[i,j] for i in range(0,7)) <= 1)
# Un chiffre n'est associé qu'à une seule lettre
for i in range(7) :
    p.add_constraint(sum(v[i,j] for j in range(0,8)) == 1)
# le modèle génère 80 variables, les retenues seront notées au delà
# D + E = Y + 10 C_1
p.add_constraint(sum(j*v[3,j] for i in range(0,7))+sum(j*v[1,j] for i in range(0,7))==sum(j*v[7,j] for i in range(0,7))+10*v[8,8])
# C_1 + R + N = E + 10 C_2
p.add_constraint(v[8,8]+sum(j*v[6,j] for i in range(0,7))+sum(j*v[2,j] for i in range(0,7))==sum(j*v[1,j] for i in range(0,7))+10*v[9,8])
# C_2 + E + O = N + 10 C_3
p.add_constraint(v[9,8]+sum(j*v[5,j] for i in range(0,7))+sum(j*v[1,j] for i in range(0,7))==sum(j*v[2,j] for i in range(0,7))+10*v[10,8])
# C_3 + S + M = O + 10 C_4
p.add_constraint(v[10,8]+sum(j*v[0,j] for i in range(0,7)) + sum(j*v[2,j] for i in range(0,7))==sum(j*v[7,j] for i in range(0,7))+10*v[11,8])
# C_4 = M
p.add_constraint(v[11,8]==sum(j*v[4,j] for i in range(0,7)))
p.show()
p.solve()
xx=p.get_values(v)
show(xx)

Obviously there is a mistake in my code that appears clearly with p.show(). The $j*V_{i,j}$ are evaluated outside of the context. Secondly, the code would be more readable if I could replace the sums by the letters. I think the evaluation must be postponed but I dont know how.