3 ms·

But WHY are they trivial? Because we can extract metadata that help us prune the solution pool? And if that's the case for the KNAPSACK problem, does this hold

by antics 16y ago

But WHY are they trivial? Because we can extract metadata that help us prune the solution pool? And if that's the case for the KNAPSACK problem, does this hold for all such problems?

jlouis 16y ago
Yes, the idea is to look at the structure of the problem and use the structure to prune the solution pool aggressively. The usual method is Branch-and-bound algorithms, but the wikipedia article does not seem to convey the idea especially well, so dig around for a better reference. Sometimes we are lucky however and there is more structure to a problem than what BB-algorithms usually give. For KNAPSACK, remember that we have a burglar with a knapsack who has just broken into a house. Each item in the house has a given profit and a given weight. The problem is to maximize the profit while still keeping the weight low enough to be in the knapsack. In the 0-1 KNAPSACK problem, there is only one of each item, so we either have to leave it, 0, or to pick it, 1. The inherent structure is that we can order the items by the ratio p/w of the profit over their weight. Item with a high p/w ratio tend to be items we need in the knapsack, whereas elements with a low p/w ratio tend not to be. It turns out you can preprocess and prune some elements this way before you start on the BB algorithm. But for this problem it turns out that there is a critical item, the break item and a window of items around it. If you can identify this window, solving that is enough for solving the whole knapsack problem. There is a theorem from the 80'es stating this. It turns out that for knapsack problems with thousands of items, the window tend to be fairly small, some 20-30 items. Pisingers codes work by being extremely clever at finding the window. It is a smart BB/Dynprog hybrid and as soon as the window is found, it is almost done. Of course, there are knapsack instances where the window is almost all of the item set and then the algorithm fail. But it turns out to be rather hard producing an instance from a real-world problem which exhibit the large window structure. Hell, Pisingers codes are often faster than sorting the items by the p/w ratio - which makes for a great discussion on complexity :) So what did I mean by trivial instances? In the SUBSET-SUM problem, this is a trivial instance: {-3,-2,-1,1,2,3}. This one too: {1,2,-3}. Or how about this one: {1,-1, 337}. In the first two, the whole set works. In the latter, it is easy to see that 337 can never be part of the sum as its inclusion lead to a value so great we can never hope to get back to 0. Even if we construct extremely large sets, it is easy to construct them in a way such they can be pruned down to a small set and then solved.
- antics 16y ago
  You have been most helpful. Thank you indeed.

by antics 16y ago

But WHY are they trivial? Because we can extract metadata that help us prune the solution pool? And if that's the case for the KNAPSACK problem, does this hold for all such problems?

jlouis 16y ago

Yes, the idea is to look at the structure of the problem and use the structure to prune the solution pool aggressively. The usual method is Branch-and-bound algorithms, but the wikipedia article does not seem to convey the idea especially well, so dig around for a better reference. Sometimes we are lucky however and there is more structure to a problem than what BB-algorithms usually give. For KNAPSACK, remember that we have a burglar with a knapsack who has just broken into a house. Each item in the house has a given profit and a given weight. The problem is to maximize the profit while still keeping the weight low enough to be in the knapsack. In the 0-1 KNAPSACK problem, there is only one of each item, so we either have to leave it, 0, or to pick it, 1. The inherent structure is that we can order the items by the ratio p/w of the profit over their weight. Item with a high p/w ratio tend to be items we need in the knapsack, whereas elements with a low p/w ratio tend not to be. It turns out you can preprocess and prune some elements this way before you start on the BB algorithm. But for this problem it turns out that there is a critical item, the break item and a window of items around it. If you can identify this window, solving that is enough for solving the whole knapsack problem. There is a theorem from the 80'es stating this. It turns out that for knapsack problems with thousands of items, the window tend to be fairly small, some 20-30 items. Pisingers codes work by being extremely clever at finding the window. It is a smart BB/Dynprog hybrid and as soon as the window is found, it is almost done. Of course, there are knapsack instances where the window is almost all of the item set and then the algorithm fail. But it turns out to be rather hard producing an instance from a real-world problem which exhibit the large window structure. Hell, Pisingers codes are often faster than sorting the items by the p/w ratio - which makes for a great discussion on complexity :) So what did I mean by trivial instances? In the SUBSET-SUM problem, this is a trivial instance: {-3,-2,-1,1,2,3}. This one too: {1,2,-3}. Or how about this one: {1,-1, 337}. In the first two, the whole set works. In the latter, it is easy to see that 337 can never be part of the sum as its inclusion lead to a value so great we can never hope to get back to 0. Even if we construct extremely large sets, it is easy to construct them in a way such they can be pruned down to a small set and then solved.

antics 16y ago
You have been most helpful. Thank you indeed.