MTM not giving global optimum solution

[jmyrberg]

For some reason, MTM is not always giving the global optimal solution - example code below:

import numpy as np

from mknapsack import solve_multiple_knapsack


weights = np.array([150609, 267741, 555412, 9398, 182512, 188255, 29982, 152993, 43347, 5490, 280600, 14600, 61927, 24200, 23729, 23729, 24719, 25667, 25667, 24293, 10242, 10242, 20984, 20984, 24441, 18031, 18030, 7898, 82960, 43188, 89792, 502728, 24608, 19880, 83843, 34123, 125813, 50340, 381556, 34374, 138632, 358680, 579318, 1137092, 233064, 363295, 110900, 85278, 30500, 59760, 34986, 220448, 405249, 136640, 37493, 486623, 215906, 33550, 45018, 217336, 42152, 360046, 159339])
capacities = np.array([152539, 344037, 1536902, 1485689, 1343247, 816366, 134575, 126148, 781097, 2411963])
profits = weights.copy()

res = solve_multiple_knapsack(
    profits,
    weights,
    capacities,
    method="mtm", 
    method_kwargs={"max_backtracks": -1},
    verbose=True
)

# res total profit = 9127272

# The following feasible solution gives profit of 9132563
res2 = np.array([3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 7, 7, 7, 0, 7, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 8, 8, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 10, 6, 9, 9, 9, 9, 6, 6, 6, 6])

[Theelx]

I can provide an example where MTHM gives significantly more evenly distributed results than MTM on mknapsack 1.1.12. The profit for every X being assigned is 1 (unfortunately I cannot specify what X and Y are). I'm not sure if the goal of either algorithm is to produce evenly distributed results, but X being distributed among Y as evenly as possible would be the optimal result for our use case. Try running the script below with method="mtm" vs method="mthm" and you'll see that the standard deviation is higher with method="mtm".

# https://github.com/jmyrberg/mknapsack
import numpy as np
from mknapsack import solve_multiple_knapsack as smk

X_SIZES = {0: 385, 1: 2546, 2: 1080, 3: 2534, 4: 1314, 5: 802, 6: 928, 7: 2960, 8: 398, 9: 1927, 10: 1071, 11: 4377, 12: 3666, 13: 1392, 14: 784, 15: 1090, 16: 1130, 17: 528,
    18: 2840, 19: 1397, 20: 783, 21: 774, 22: 814, 23: 2862, 24: 2392, 25: 1685, 26: 868, 27: 139, 28: 719, 29: 352, 30: 273, 31: 4964, 32: 621, 33: 1262, 34: 5372, 35: 551,
    36: 1327, 37: 244, 38: 1264, 39: 1201, 40: 2406, 41: 367, 42: 879, 43: 690, 44: 5787, 45: 1287, 46: 425, 47: 598, 48: 69, 49: 1202, 50: 711, 51: 2181, 52: 661,
    53: 1226, 54: 4708, 55: 931, 56: 1249, 57: 642, 58: 543, 59: 4521, 60: 8146, 61: 546, 62: 1000, 63: 3402, 64: 4232, 65: 3363, 66: 8690, 67: 8664, 68: 5043, 69: 8711,
    70: 2792, 71: 7470, 72: 1231, 73: 3243, 74: 5808, 75: 2736, 76: 5532, 77: 855, 78: 6760, 79: 6861, 80: 786, 81: 2513, 82: 1261, 83: 6102, 84: 2133, 85: 1640,
}

WEIGHTS_PER_Y = {
    "y1": 0,
    "y2": 1,
    "y3": 1,
    "y4": 1,
    "y5": 1.5,
    "y6": 1.5,
    "y7": 1,
    "y8": 1,
    "y9": 1,
    "y10": 1,
    "y11": 1,
}

NUM_Y = len(WEIGHTS_PER_Y)

TOTAL_X = sum(X_SIZES.values())
WEIGHT_SUM = sum(WEIGHTS_PER_Y.values())
TARGET_X_PER_WEIGHT = TOTAL_X // WEIGHT_SUM
TARGET_X = [
    weight * TARGET_X_PER_WEIGHT for weight in list(WEIGHTS_PER_Y.values())
]
for _ in range(TARGET_X.count(0)):
    TARGET_X.remove(0)
TARGET_X_PER_Y = TOTAL_X / len(TARGET_X)

print(
    f"Total x: {TOTAL_X}\nTarget x for y: {TARGET_X}\nAverage target x: {TARGET_X_PER_Y}"
)

weights = list(X_SIZES.values())
profits = [1 for _ in range(len(weights))]
res = smk(
    profits,
    weights,
    TARGET_X,
    method="mtm",
    method_kwargs={"max_backtracks": -1},
    verbose=True,
)

nums1 = np.array(list(X_SIZES.keys()))

print("\nResults:\n")

stddev1 = []
stddevall = []

for indx, (Y, value) in enumerate(WEIGHTS_PER_Y.items()):
    nums = sorted(nums1[res == (indx)])
    if value == 1:
        stddev1.append(sum(X_SIZES[num] for num in nums))
    stddevall.append(sum(X_SIZES[num] for num in nums))
    print(
        f"total x for {Y}: {sum(X_SIZES[num] for num in nums)}"
    )

print(np.std(np.array(stddev1))) # mtm: 723.1997908600362, mthm: 73.18256281382881
print(np.std(np.array(stddevall))) # mtm: 4954.355409199178, mthm: 4042.1631554412315