KnapsackDivideAndConquerSolver

[ruqzuq]

Bonjour

the discussion refers to the PR: 2506

I would like to jointly weigh the use of an additional solver that solves one-dimensional (KP) in O(cN) Time and O(c+N) Space optimal. Like KnapsackDynamicProgrammingSolver, the technique builds on DP-2 [1], but unlike DP-3, it does not iterate all items in the worst case, but instead bounds the sub-problems by divide and conquer.

The KnapsackDynamicProgrammingSolver also has a Space Complexity of O(c + N), but it loses this with a Time Complexity of O(c(N)^2).

However, I don't think it makes sense to replace DP-3. It performs outstandingly well for certain (KP)/(SSP), even if |n| is very large. However, it can become unusable even at low |n|.

I have tested KDACS and KDPS overnight in several constellations. Because both have a linear space complexity, large |n| can be tested, if they are easy to solve for KDPS: e.g. for (SSP) with small items KDPS performs very well and on average beats KDACS in half the time even for larger |n| > 1,000,000 and c > 100,000,000.

In summary, KDACS has a running time of 2|n|c for all (KP) according to (3.1) [1] and its efficient memory consumption makes it a useful candidate if one wants to solve very large hard to solve (KP).

[1] Kellerer et al., "Knapsack Problems"

[lperron]

IN your PR, you should add that this is an approximate approach that does not guarantee optimality.

[ruqzuq]

I am unclear how you mean this. Does it refer to the algorithm or the implementation?

[lperron]

The algorithm is not exact. It returns a good but not optimal solution. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le jeu. 15 avr. 2021 à 15:27, ruqzuq ***@***.***> a écrit :

…

I am unclear how you mean this. Does it refer to the algorithm or the implementation? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2507 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3IYLFEWCWEOYTSKVLTTI3STVANCNFSM427KQ6RA> .

[ruqzuq]

My naming is bad. There are approximation schemes that are so named. The real name of DP-2 with storage reduction is RECURSIVE-DP. But the name does not matter for me, I took DivideAndConquerSolver as a placeholder, because it describes the procedure. You can name it.

[lperron]

back to basics. Knapsack is NP-Hard you cannot solve it exactly with a polynomial algorithm. You can also look at: https://link.springer.com/content/pdf/10.1007/s10878-020-00584-2.pdf The abstract clearly states that the algorithm is not exact. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le jeu. 15 avr. 2021 à 16:41, ruqzuq ***@***.***> a écrit :

…

My naming is bad. There are approximation schemes that are so named. The real name of DP-2 with storage reduction is RECURSIVE-DP. But the name does not matter for me, I took DivideAndConquerSolver as a placeholder, because it describes the procedure. You can name it. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2507 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3IBASKRHKEYLTRRYNLTI33LFANCNFSM427KQ6RA> .

[ruqzuq]

Yes, but with a non-polynomial(pseudo polynomial) algorithm.

We can solve (KP) in O(cN) Time with DP exactly. But we have a cN vector for backtracking so O(cN) Space. To be exact, we solve it in cN Time and cN Space.

You reduces Space to O(c+N) with DP-3, but increases Time to O(c(N)^2).

DP-Rec also reduces Space to O(c+N), but remains in O(cN) Time. Its 2cN Time to be exact. So it takes twice time to solve compared to DP, but we dont need a 2d vector for backtracking and are abled to solve millions of items.

[ruqzuq]

test it :)

[lperron]

I do not like the tone of this thread. This is not a contest.

[ruqzuq]

Excusez-moi.

I have provided the necessary details for a factual discussion. I am willing to explain all the details. Nevertheless, I cannot deal with misinformation. If there is no interest in external volunteer involvement, I respect that and leave the project in silence.

I compared the two solvers to visualize the runtime of DP-3 and Rec-DP. In doing so, I adjusted the input to match the way DP-3 works. The profits/weights are randomly generated, the coefficient profit/weight increases minimally with larger index. This forces DP-3 to iterate especially at the beginning often DP-2 with large num_items. Thus the actual running time becomes apparent as described above.

[lperron]

There is interest. This approach works really well. It is not polynomial, but pseudo-polynomial. It does not always win against other approaches, but worth it. I do not like how the papers are often misleading in the exact complexity. This O(cW) is tricky. I still do not understand exactly where you can hit the underlying exponential. I will approve the PR. Thanks for the 'lively' discussion :-) Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le ven. 16 avr. 2021 à 12:24, ruqzuq ***@***.***> a écrit :

…

Excusez-moi. I have provided the necessary details for a factual discussion. I am willing to explain all the details. Nevertheless, I cannot deal with misinformation. If there is no interest in external volunteer involvement, I respect that and leave the project in silence. I compared the two solvers to visualize the runtime of DP-3 and Rec-DP. In doing so, I adjusted the input to match the way DP-3 works. The profits/weights are randomly generated, the coefficient profit/weight increases minimally with larger index. This forces DP-3 to iterate especially at the beginning often DP-2 with large num_items. Thus the actual running time becomes apparent as described above. [image: comparison] <https://user-images.githubusercontent.com/82470542/115011094-7dfa8400-9eae-11eb-84d6-a6118afeab5d.png> — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2507 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3JYI462LHNU6ESWBXDTJAF5HANCNFSM427KQ6RA> .

[ruqzuq]

I understand 'underlying exponential' in relation to DP-3. I'll have time tomorrow and describe it in a new discussion or so. It took me about 4 hours and a night to understand the performance from the DynamicProgrammingSolver. On one side are optimizations from the compiler that falsify trivial tests. For example, a non-trivial test I used looks like this:

(in my test, you can prevent the exponential by sorting beforehand. But you can't predict the order optimally greedily due to NP heaviness, and in complex problems a running time of cNk is relatively likely, where k is the number of elements iterated at the beginning. So DP-3 has a BB similar behavior, with the extreme points differing)

namespace random_ {
// generate vector with random filled values
void randomVector(std::vector<int64_t>& rVector, int range_) {
// assign random int
for (int i = 0; i < rVector.size(); i++) rVector[i] = rand() % range_ + 1;
}
}

/////////namespace xy_
///////////////////////////////////
//seed = number of items
//////////////////////////////////
int seed = 10;

std::vector<int64_t> values(seed);
random_::randomVector(values, 500);

std::vector<std::vector<int64_t>> weights(1);
weights[0] = values;

double divis = seed;

for (int i = 0; i < values.size(); i++) {
weights[0][i] = weights[0][i] * (divis / seed);

divis *= 0.999;
}

std::vector<int64_t> capacities = {seed * 200};