Open jmyrberg opened 1 year ago
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
For some reason, MTM is not always giving the global optimal solution - example code below: