Ask Your Question
0

SEND+MORE=MONEY (Milp programming)

asked 2019-11-18 08:08:50 -0500

Cyrille gravatar image

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.

edit retag flag offensive close merge delete

Comments

BTW when using range() you can just write range(7) with one argument--in this case the 0, is implied.

Iguananaut gravatar imageIguananaut ( 2019-11-18 10:21:15 -0500 )edit

Yes I know but in all cases thanks to make the remarks. Initialy , I was beginning at 1.

Cyrille gravatar imageCyrille ( 2019-11-18 15:02:02 -0500 )edit

1 answer

Sort by » oldest newest most voted
1

answered 2019-11-18 11:07:09 -0500

tmonteil gravatar image

updated 2019-11-18 11:07:47 -0500

I don't know the problem, but when you write things like sum(j*v[3,j] for i in range(0,7)) are you sure that you do not confuse i and j ?

edit flag offensive delete link more

Comments

tmonteil I have corrected the code and it seems to work. I wonder if there is a way to get only the v values equal to 1.

Cyrille gravatar imageCyrille ( 2019-11-18 16:22:40 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-11-18 08:08:50 -0500

Seen: 78 times

Last updated: Nov 18 '19