jmyrberg / mknapsack Goto Github PK

What is the meaning of the output?

The testcase in the README resulted in

Total profit: 376
Solution: [0, 0, 1, -1, 0, -1, -1, -1, 1, -1]
Number of backtracks performed: 29
Global optimum: 1

I presume the solution 0,1 means which bag and -1 means not included. Is that correct? Moreover, what does global optimum mean?

If I am not mistaken, that would mean the selected weights are: 18+9+23+59+76=185 and total profit is 78+35+89+94+80=376. That seems to be it. It would be good to have some sort of explanation like this in the README.

However, the aforementioned result is not optimal. Apparently the solution would be the following:

weights: 18+9+23+20+59+61=190
profit: 78+35+89+36+94+75=407

Am I doing anything wrong?

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])

Examine if wheels could be built in CICD and provided from PyPi instead of building from source like now

I noticed there are installation instructions, but no uninstallation instructions.

As this package is installed via distutils, it cannot simply be uninstalled by doing pip uninstall mkp

When I test a case, it raise a "ValueError: Solution not valid". It seems like a bug when doing "Ensure solution validity".

from mknapsack.algorithms import mtm
profits = [1,1]
weights = [1,1]
capacities = [2,2]

z, x, bt, glopt = mtm(profits, weights, capacities)
print('Total profit: %d' % z)
print('Solution: %s' % x)
print('Number of backtracks performed: %d' % bt)
print('Global optimum: %s' % glopt)

The error is:
ValueError: Solution not valid:
p w c valid
i
0 2 2.0 2 1

How to solve this problem？

E.g. if the total weight is smaller than largest knapsack, provide a trivial solution instead of throwing an error.

Hi,

Sorry if this issue seems a bit stupid,
But when I try to run:

from mknapsack import solve_multiple_knapsack

res = solve_multiple_knapsack(
                profits=[25032,17185,57704,64358,11089,5354,3401,45784,9435,28668,41243,57777,9916,25841,36636,49305,37458,55364,40134,44312,3888,44793,6749,65862,67072,54439,57334,51055,49393,26305,35357,67324,64537,65625,56649,54558,28625],
                weights=[653250,965773,944737,671036,601642,1274815,1140173,996544,918682,889250,880779,775219,805400,911355,949676,1270782,687677,1049923,844992,581054,645960,517639,1211440,691625,839166,678857,1223638,564127,695884,479706,620077,709761,667338,646920,996692,729103,530888],
                capacities=[760918113,550545288,554599425,557182218,609915305,761528614,775865259,524277499,538024903,767863544,328247677,570234149,641681870,606040298,692398729,593140773,658394446,697797771,559652541,574848244]
            )

print( res )

I get:

┌──(user㉿dhcppc4)-[~/Desktop/mknapsack]
└─$ python test.py     
Traceback (most recent call last):
  File "/home/user/Desktop/mknapsack/test.py", line 3, in <module>
    res = solve_multiple_knapsack(
  File "/home/user/.local/lib/python3.10/site-packages/mknapsack/_multiple.py", line 174, in solve_multiple_knapsack
    raise FortranInputCheckError(method=method, z=z)
mknapsack._exceptions.FortranInputCheckError: Total sum of weights is smaller than largest knapsack

Now,

Total sum of weights is smaller than largest knapsack

Why? Seems to me It is ok if sum of weights is smaller than largest knapsack in some scenario...

I also tried changing the method to "mthm" but I figured its limit is set up to 10 knapsacks.

UPDATE:

Using method_kwargs={"check_inputs": 0} resolved the issue, but I'm still interested to find out that why would the total sum of weights being greater than largest knapsack is a problem?

Ensure correct errors are thrown regarding problem size limitations before trying to solve it within Fortran

Hello, and thanks so much for this amazing library! I spent many hours googling and looking through StackOverflow for efficient ways to solve the Multiple Knapsack problem with approximate solutions, and yours is by far the fastest and easiest to use.

I have some code where I'm trying to distribute work among three people (no more, no less). All work pieces must be distributed to someone. Each weight's value represents the amount of work one person must do (1000 represents ~1000 seconds of work, though the units are irrelevant), and the targets are the amount of work each person should do, with the same units as the weights. The issue is that solve_multiple_knapsack somehow seems to be making a fourth knapsack, which is weird because I'm only providing it three capacities. A Minimal Reproducible Example is as follows:

from mknapsack import solve_multiple_knapsack
import numpy as np

weights = np.array([1000, 3402, 4232, 3363, 8690, 8664, 5043, 8711, 2792, 7470, 1231, 3243, 5808, 2736, 5532, 855, 6760, 6861, 786, 2513, 1261, 6102, 2133, 1640])
profits = np.array([1 for _ in range(len(weights))])
capacities = np.array([50414, 25207, 25207])
res = solve_multiple_knapsack(profits, weights, capacities)
print(res)
print(np.sum(sizes[res == 0]), np.sum(sizes[res == 1]), np.sum(sizes[res == 2]), np.sum(sizes[res == 3]))
# Output:
# [1 2 1 3 3 1 2 0 2 2 1 1 3 1 1 1 1 3 1 1 1 2 1 1]
# 8711 42586 24809 24722

# Expected output:
# [1 2 1 3 3 1 2 1 2 2 1 1 3 1 1 1 1 3 1 1 1 2 1 1]
# 59217 24809 24722
# or
# Exception! Input values cannot be split without exceeding the capacity of a knapsack! Pass force=True to return an extra knapsack with the extra values.

I'm guessing this is because there's some assumption in the code that the result values are never allowed to go over the knapsacks' capacities. While this makes sense with the normal formulation of the problem, in my case one person can take slightly more work than the capacity as long as all the weights are assigned to someone.

Basically, I'm wondering if:

1. I'm using the correct solver for my case. If possible, I'd appreciate a recommendation for a better solver if I'm using the wrong one.
2. It makes sense for the result to implicitly contain an extra knapsack without warning the user or documenting the behavior in the README. It seems especially liable to issues if the user uses the results in a pipeline, where they don't see the results immediately, and where there may or may not be an extra knapsack. A better design may be to put the extra knapsack at the end position instead of position 0.

Thanks in advance!

This is my case:

std::vector<int> profits7 = {700, 600, 500, 400, 400, 300, 300, 300, 300, 300, 200, 200, 100, 100};
std::vector<int> weights7 = {7, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1};
std::vector<int> capacities7 = {8, 8, 8, 8, 8, 8};

Howerver, when I run the main.cpp, the program was stopped with "segmentation fault".

I debug the program and found the error was array out of bound in mtm_c.cpp:153. The variable 'il' is negative.

I don't quite understand the meaning of variable "il". How to solve this problem?