Revision history [back]

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

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

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']))