Ask Your Question
0

SEND+MORE=MONEY (one more time)

asked 2019-12-03 09:01:23 -0600

Cyrille gravatar image

updated 2019-12-04 09:05:27 -0600

I have some heavy problems of formulation with Sagemath. It's certainly a formulation problem --- I will add the theoretrical aspect of the model at the end of the question :

I have corrected my code. May be some errors could stay. But even if I am wrong I need some information on how to write my program. You can find the source in the free paper https://pubsonline.informs.org/doi/pd.... There is also an Excel code on the internet. Here is my code

p = MixedIntegerLinearProgram(maximization=True,solver='PPL')
v = p.new_variable(nonnegative=True)# permet de définir v[i, j] aussi bien que v[i]
c = p.new_variable(nonnegative=True)# permet de définir v[i, j] aussi bien que v[i]
p.set_objective(v[0,0])
for i in range(7) : # nombre de lettres (8)
        for j in range(9) : #nombre de chiffres
            p.set_binary(v[i,j])
#S=sum(j*v[0,j] for j in range(9))
#E=sum(j*v[1,j] for j in range(9))
#N=sum(j*v[2,j] for j in range(9))
#D=sum(j*v[3,j] for j in range(9))
#M=sum(j*v[4,j] for j in range(9))
#O=sum(j*v[5,j] for j in range(9))
#R=sum(j*v[6,j] for j in range(9))
#Y=sum(j*v[7,j] for j in range(9))

for k in range(1,4) :
    p.set_binary(c[k])

# Une lettre n'est représentée que par un chiffre
for j in range(8) :
    p.add_constraint(0<= sum(v[i,j] for i in range(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(9)) == 1)

# D + E = Y + 10 C_1
p.add_constraint(sum(j*v[3,j] for j in range(7))+sum(j*v[1,j] for j in range(9))==
                 sum(j*v[7,j] for j in range(7))+10*c[1])#
# C_1 + R + N = E + 10 C_2
p.add_constraint(c[1]+sum(j*v[6,j] for j in range(7))+sum(j*v[2,j] for j in range(9))==
                 sum(j*v[1,j] for j in range(9))+10*c[2])#
# C_2 + E + O = N + 10 C_3
p.add_constraint(c[2]+sum(j*v[5,j] for j in range(8))+sum(j*v[1,j] for j in range(9))==
                 sum(j*v[2,j] for j in range(9))+10*c[3])#
# C_3 + S + M = O + 10 C_4
p.add_constraint(c[3]+sum(j*v[0,j] for j in range(9)) + sum(j*v[4,j] for j in range(9))==
                 sum(j*v[5,j] for j in range(9))+10*c[4])#
# C_4 = M
p.add_constraint(c[4]==sum(j*v[4,j] for j in range(9)))
p.solve()
p.show()

xx=p.get_values(v)
show(xx)
for j in range(9) :
    if xx[0,j]== 1 : print('S='+ `j`) 
for j in range(9) :
    if xx[1,j]== 1 : print('E='+ `j`)         
for j in range(9) :
    if xx[2,j]== 1 : print('N='+ `j`)
for j in range(9) :
    if xx[3,j]== 1 : print('D='+ `j`)
for j in range(9) :
    if xx[4,j]== 1 : print('M='+ `j`)
for j in range(9) :
    if xx[5,j]== 1 : print('O='+ `j`)
for j in range(9) :
    if xx[6,j]== 1 : print('R='+ `j`)
for j in range(9) :
    if xx[7,j]== 1 : print('Y='+ `j`)

I have 8x10 = 80, v[i,j] variables v[i, j] and 4 c[j] variables. I have asked all to be binary. But when I look the printed model I see only 73 variables and from $x_{66}$ to $x_{73}$ they are not binary. More than that the (7,6) variables takes a value of 3/6. It's not particularly simple to associate the variables internal variables to the internal ones.

I need help! (Thanks by advance). The documentation is of no help for me.

MODELIZATION CLUES

In this so called "cryptarythm" one use 8 letters $S_{(1)}E_{(2)}N_{(3)}D_{(4)}M_{(5)}O_{(6)}R_{(7)}Y_{(8)}$ so we define the binary variables

$x_{ij} = \begin{cases} 1 & \text{if letter } i (i= 1, \ldots 8) \text{ is associated to th digit } j (j = 0,\ldots, 9)\\ 0 & \text{sinon} \end{cases}$

We need also 4 variables $C_k$ for the retention. From this one can write $S = \sum_{1}^9 j x_{1j }$, $E = \sum_{1}^9 j x_{2j }$ and so on. For the constraints one have 17 general constraints

--- each letter is associated to a unic digit $\sum_{j=0}^9 x_{ij} = 1, \text{ for } i = 1, \ldots 8$
--- each digit is associated to a only one letter $\sum_{i=0}^8 x_{ij} \leq 1, \text{ for } j = 1, \ldots 9$

Then one hase the pure addition constraints :

$D + E = Y + 10 C_1 \Longleftrightarrow \sum_{j=0}^9 j x_{2j} +\sum_{j=0}^9 j x_{4j}= \sum_{j=0}^9 j x_{8j} + 10 C_1$

$C_1 + R + N = Y + 10 C_2 \Longleftrightarrow C_1+\sum_{j=0}^9 j x_{3j} +\sum_{j=0}^9 j x_{4j}= \sum_{j=0}^9 j x_{2j} + 10 C_2$

$C_2 + E + O = N + 10 C_3 \Longleftrightarrow C_2+\sum_{j=0}^9 j x_{2j} +\sum_{j=0}^9 j x_{6j}= \sum_{j=0}^9 j x_{3j} + 10 C_3$

$C_3 + S + M = O + 10 C_4 \Longleftrightarrow C_3+\sum_{j=0}^9 j x_{1j} +\sum_{j=0}^9 j x_{5j}= \sum_{j=0}^9 j x_{6j} + 10 C_4$

$C_4 = M \Longleftrightarrow C_4 = \sum_{j=0}^9 j x_{5j}$

Here is the solution

$(S=9). (E=5). (N=6). (D=7).$

$+. (M=1). (O=0).(R=8). (E=5).$

$= (M=1). (O=0). (N=6). (E=5). (y=2)$

edit retag flag offensive close merge delete

Comments

If all variables are binary, you can do directly

v = p.new_variable(binary=True)
c = p.new_variable(binary=True)

Can you give more details on the problem (input, output, objective, constraints) in text, not code.

David Coudert gravatar imageDavid Coudert ( 2019-12-04 01:24:08 -0600 )edit

Sorry David, I have just seen your commentarySEND+MORE = MONEY is an exemple of a game which consists to substitute a letter to a decimal digit You can find the substitution by logical reasoning. Here we try to model tje problem as a feasibility test. I will see if I could add in my question the theory.

Cyrille gravatar imageCyrille ( 2019-12-04 07:23:21 -0600 )edit

1 answer

Sort by » oldest newest most voted
1

answered 2019-12-06 02:28:09 -0600

updated 2019-12-06 08:53:49 -0600

I tried the following and it's working well with all solvers (PPL, GLPK, Cplex, etc.). However, if I specify the type of the c variables (e.g., c = p.new_variable(integer=True, name='c')), then PPL is no longer able to return a solution

def send_more_money(solver='PPL', verbose=False):
    p = MixedIntegerLinearProgram(maximization=True, solver=solver)
    v = p.new_variable(binary=True, name='v')
    c = p.new_variable(name='c')

    letters = list(range(1, 9))  # [1, 2, 3, 4, 5, 6, 7, 8]
    digits = list(range(10))  # 0, 1, .., 9

    # Maximum matching, or all diff

    # a letter corresponds to a unique digit
    for i in letters:
        p.add_constraint(p.sum(v[i,j] for j in digits) == 1)
    # a digit is assigned to at most one letter
    for j in digits:
        p.add_constraint(p.sum(v[i,j] for i in letters) <= 1)

    # D + E = Y + 10*C1
    p.add_constraint(p.sum(j * v[4,j] for j in digits) + p.sum(j * v[2,j] for j in digits)
                         == p.sum(j * v[8,j] for j in digits) + 10 * c[1])
    # C1 + N + R = E + 10*C2
    p.add_constraint(c[1] + p.sum(j * v[3,j] for j in digits) + p.sum(j * v[7,j] for j in digits)
                         == p.sum(j * v[2,j] for j in digits) + 10 * c[2])
    # C2 + E + O = N + 10*C3
    p.add_constraint(c[2] + p.sum(j * v[2,j] for j in digits) + p.sum(j * v[6,j] for j in digits)
                         == p.sum(j * v[3,j] for j in digits) + 10 * c[3])
    # C3 + S + M = 0 + 10*C4
    p.add_constraint(c[3] + p.sum(j * v[1,j] for j in digits) + p.sum(j * v[5,j] for j in digits)
                         == p.sum(j * v[6,j] for j in digits) + 10 * c[4])

    # Maximize M
    p.set_objective(p.sum(j * v[5,j] for j in digits))

    p.solve(log=verbose)
    x = p.get_values(v)

    for i, l in zip(letters, ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']):
        print("{} = {}".format(l, sum(j * x[i,j] for j in digits)))

    xx = {l : sum(j * x[i,j] for j in digits)
              for i, l in zip(letters, ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y'])}

    print("    {} {} {} {}".format(xx['S'], xx['E'], xx['N'], xx['D']))
    print("+   {} {} {} {}".format(xx['M'], xx['O'], xx['R'], xx['E']))
    print("= {} {} {} {} {}".format(xx['M'], xx['O'], xx['N'], xx['E'], xx['Y']))

Solution:

sage: send_more_money()
S = 3
E = 5
N = 7
D = 8
M = 9
O = 0
R = 1
Y = 2
    3 5 7 8
+   9 0 1 5
= 9 0 7 5 2

EDIT: nicer way to write it

def send_more_money(solver='PPL', verbose=False):
    p = MixedIntegerLinearProgram(maximization=True, solver=solver)
    v = p.new_variable(binary=True, name='v')
    c = p.new_variable(name='c')

    letters = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
    digits = list(range(10))  # 0, 1, .., 9

    # a letter corresponds to a unique digit
    for i in letters:
        p.add_constraint(p.sum(v[i,j] for j in digits) == 1)
    # a digit is assigned to at most one letter
    for j in digits:
        p.add_constraint(p.sum(v[i,j] for i in letters) <= 1)

    f = lambda l: p.sum(j * v[l,j] for j in digits)

    p.add_constraint(       f('D') + f('E') == f('Y') + 10 * c[1])
    p.add_constraint(c[1] + f('N') + f('R') == f('E') + 10 * c[2])
    p.add_constraint(c[2] + f('E') + f('O') == f('N') + 10 * c[3])
    p.add_constraint(c[3] + f('S') + f('M') == f('O') + 10 * c[4])
    p.set_objective(                           f('M'))

    p.solve(log=verbose)

    x = p.get_values(v)

    for l in letters:
        print("{} = {}".format(l, sum(j * x[l,j] for j in digits)))

    xx = {i : sum(j * x[i,j] for j in digits) for i in letters}

    print("    {} {} {} {}".format(xx['S'], xx['E'], xx['N'], xx['D']))
    print("+   {} {} {} {}".format(xx['M'], xx['O'], xx['R'], xx['E']))
    print("= {} {} {} {} {}".format(xx['M'], xx['O'], xx['N'], xx['E'], xx['Y']))
edit flag offensive delete link more

Comments

David Coudert, thanks a lot. It's will be a mine to learn for me

Cyrille gravatar imageCyrille ( 2019-12-06 02:34:41 -0600 )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-12-03 09:01:23 -0600

Seen: 114 times

Last updated: Dec 06 '19