-
Notifications
You must be signed in to change notification settings - Fork 14
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
MTM not giving global optimum solution #50
Comments
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 # 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:
The text was updated successfully, but these errors were encountered: