Fork me on BitBucket
Filter:
2011-11-05

linear programming

Another Project Euler problem:

Given a matrix (15 by 15 grid of numbers), what is the maximum sum of numbers achievable with the restriction that.. You may only pick one number from each row. Also none of the numbers picked are allowed to be in the same column!

After looking at the problem I decided I could use either integer programming or dynamic programming (or perhaps even backtracking with pruning).

I'd been told how easy it is to use pythons PULP linear programming library so thought i'd give it a shot and it did turn out to be remarkably simple to use, here is the solution in fact:

__author__ = 'Robert'
import pulp

def get_lp_problem(matrix):
    prob = pulp.LpProblem("pe345", pulp.LpMaximize)
    cols = [[] for i in range(15)]
    rows = [[] for j in range(15)]
    objective = []
    for i in range(15):
        for j in range(15):
            var = pulp.LpVariable('{i}_{j}'.format(i=i, j=j),
                lowBound=0, upBound=1,
                cat=pulp.LpInteger)
            cols[i].append(var)
            rows[j].append(var)
            profit = matrix[i][j]
            objective.append(profit * var)
    for col in cols:
        prob += sum(col) <= 1 #1 value per col
    for row in rows:
        prob += sum(row) <= 1 #1 value per row
    prob += sum(objective) #objective function
    return prob

def solve():
    matrix = \
"""7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805"""\
    .splitlines()
    matrix = [map(int, line.split()) for line in matrix]
    lp_prob = get_lp_problem(matrix)
    lp_prob.solve()
    print lp_prob.solutionTime #0.04 seconds
    ans = 0
    for var in lp_prob.variables():
        if var.varValue > 0:
            i, j = map(int, var.name.split('_'))
            ans += matrix[i][j]
            #I don't know how to evaluate lp_prob.objective,
            # so add them manually
    return ans

print solve()

Integer Programming always seems the lazy option for solving many problems. For more Details on Linear Programming or PULP I suggest you check out this awesome example

In fact I just solved another PE problem using almost exactly the same code as above: With Problem 185 one must try to guess a number. Each guess we are told how many digits of our guess are in the correct place e.g. for
90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct
we have an answer of 39542

Here is my code that solves the larger system:

__author__ = 'Robert'
import pulp

def get_lp_problem(constraints):
    prob = pulp.LpProblem("pe345", pulp.LpMaximize)
    objective = []
    vars = {}
    for j in range(len(constraints[0][0])):
        position_restriction = []
        for i in range(10):
            var = pulp.LpVariable('{i}_{j}'.format(i=i, j=j),
                lowBound=0, upBound=1,
                cat=pulp.LpInteger)
            vars[(i, j)] = var
            #var controls if digit i occurs at position j
            objective.append(var)
            position_restriction.append(var)
        #1 digit in position j:
        prob += sum(position_restriction) <= 1

    for guess, num_correct in constraints:
        guess_constraint = []
        for j, i in enumerate(guess):
            i = int(i)
            var = vars[(i, j)]
            guess_constraint.append(var)
        prob += sum(guess_constraint) == num_correct
    prob += sum(objective) #objective function
    return prob

def solve():
    data =\
    """5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct"""
    data = data.replace(" correct", "")
    data = data.replace(";", "")
    constraints = []
    for line in data.splitlines():
        guess, num_correct = line.split()
        num_correct = int(num_correct)
        constraints.append((guess, num_correct))
    lp_prob = get_lp_problem(constraints)
    lp_prob.solve()
    print lp_prob.solutionTime #0.2 seconds
    solution = ['?'] * len(constraints[0][0])
    for var in lp_prob.variables():
        if var.varValue > 0:
            i, j = map(int, var.name.split("_"))
            solution[j] = str(i)
    return "".join(solution)

print solve()

As you can see, Once again the PULP library proved very simple to use, The code took less than ten minutes to write.




page divider

Random Quote