Maximum sum of combinations (algorithm optimization)

Question

I have a dictionary of length n choose m, with keys of tuples of length m containing all combinations of integers 1 to n. I would like to compute the maximum sum of the values of this dictionary such that the indices of the tuple keys are unique, storing the combinations that make up this maximum.

Example input:

input_dict = {
    (1, 2): 16,
    (1, 3): 4,
    (1, 4): 13,
    (1, 5): 8,
    (1, 6): 9,
    (2, 3): 6,
    (2, 4): 19,
    (2, 5): 7,
    (2, 6): 16,
    (3, 4): 12,
    (3, 5): 23,
    (3, 6): 12,
    (4, 5): 17,
    (4, 6): 19,
    (5, 6): 21
}

Example output:

(((1, 2), (3, 5), (4, 6)), 58)

My current approach: compute the sum of all unique combinations of outputs and take the maximum.

gen_results = [{}]

for (key, val) in input_dict.items():
    gen_results[0][(key,)] = val

i = 0
complete = False
while not complete:
    complete = True
    gen_results.append({})
    for (combinations, running_sum) in gen_results[i].items():
        for (key, val) in input_dict.items():
            unique_combination = True
            for combination in combinations:
                for idx in key:
                    if idx in combination:
                        unique_combination = False
                        break
                if not unique_combination:
                    break
            if unique_combination:
                complete = False
                gen_results[i+1][combinations + (key,)] = running_sum + val
    i += 1

generation_maximums = []
for gen_result in gen_results:
    if gen_result == {}:
        continue
    generation_maximums.append(max(gen_result.items(), key=(lambda x: x[1])))

print(max(generation_maximums, key=(lambda x: x[1])))

How can I improve my algorithm for large n and m?

you could use PULP or some integer programming package. A variable Xij will be 1 or 0. Add constraints. Objective function is the sum. — robert king
For the case of m=2, this is identical to a maximum weight matching problem on the complete graph of n vertices, which can be solved very efficiently with Edmons algorithm. The more general case is finding a max weight matching on an m-hypergraph. This is a much tougher problem that isn't well-studied, and which this paper appears to say is NP-complete. If that's correct, you won't get an optimal answer without work that's exponential in the input size. — Gene

robert king robert king · Accepted Answer · 2018-03-07T02:59:51

if you don't go for integer programming, you can often brute force these things using bits as hashes

e.g. the following outputs 58

input_dict = {
    (1, 2): 16,
    (1, 3): 4,
    (1, 4): 13,
    (1, 5): 8,
    (1, 6): 9,
    (2, 3): 6,
    (2, 4): 19,
    (2, 5): 7,
    (2, 6): 16,
    (3, 4): 12,
    (3, 5): 23,
    (3, 6): 12,
    (4, 5): 17,
    (4, 6): 19,
    (5, 6): 21
}
dp = {}
n, m = 2, 6
for group, score in input_dict.items():
    bit_hash = 0
    for x in group:
        bit_hash += 1 << (x-1)
    dp[bit_hash] = score

while True:
    items = dp.items()
    for hash1, score1 in items:
        for hash2, score2 in items:
            if hash1 & hash2 == 0:
                dp[hash1|hash2] = max(dp.get(hash1|hash2), score1+score2)
    if len(dp) == (1<<m)/2-1:
        print dp[(1<<m)-1]
        break

Maximum sum of combinations (algorithm optimization)

1 Answers