33

The standard 0/1 knapsack requires that the weight of every item is independent to others. Then DP is a efficient algorithm towards the solution. But now I met a similar but extensions of this problem, that

the weight of new items are dependent on previous items already in the knapsack.

For example, we have 5 items a, b, c, d and e with weight w_a, ..., w_e. item b and c have weight dependency.

When b is already in the knapsack, the weight of item c will be smaller than w_c because it can share some space with b, i.e. weight(b&c) < w_b + w_c. Symmetrically, when c is already in the knapsack, the weight of b will be smaller than w_b.

This uncertainty results a failure of original DP algorithm, since it depend on the correctness of previous iterations which may not correct now. I have read some papers about knapsack but they either have dependencies subjected to profit (quadratic knapsack problem), or have variable weight which follows a random distribution (stochastic knapsack problem). I have also aware of the previous question 1/0 Knapsack Variation with Weighted Edges, but there is only a very generic answer available, and no answer about what is the name of this knapsack.

One existing solution:

I have also read one approximate solution in a paper about DBMS optimizations, where they group the related items as one combined item for knapsack. If use this technique into our example, the items for knapsack will be a, bc, d, e, therefore there is no more dependencies between any two of these four items. However it is easy to construct an example that does not get optimal result, like when an item with "small weight and benefit" is grouped with another item with "large weight and benefit". In this example, the "small" item should not be selected in solution, but is selected together with the "large" item.

Question:

Is there any kind of efficient solving techniques that can get optimal result, or at least with some error guarantee? Or am I taking the wrong direction for modelling this problem?

Community
  • 1
  • 1
Paddy Xu
  • 518
  • 4
  • 8
  • 6
    It seems like your question got some downvotes. I don't really agree with the downvoters, but it was probably because you asked if there was any research into this problem, which could be interpreted as asking for an "off site resource" which is off topic. – samgak Aug 10 '16 at 10:17
  • 2
    @samgak Thanks for the comment. I have modified my question to be more focus onto any possible solution. – Paddy Xu Aug 10 '16 at 10:35
  • 2
    This question is [being discussed on Meta](http://meta.stackoverflow.com/q/332155/2840103). – johnnyRose Aug 11 '16 at 16:16
  • Are there any limits on the dependency? Typically, would it be possible to have dependency between all items (e.g. 3 items a, b, c, with w(a & b) != w(a) + w(b) and w(a & c) != w(a) + w(c) and w(b & c) != w(b) + w(c) and w(a & b & c) != w(a) + w(b) + w(c)). Also, are you looking for a theoretical solution or for a practical one (in which case you should add information about the size of the instances you are trying to solve). – Holt Aug 12 '16 at 11:36
  • 3
    You can try a standard B&B approach for the knapsack, you will simply have to update weights of items depending on which items are already on the knapsack when computing the upper and lower bounds (should not be that complicated). – Holt Aug 12 '16 at 11:37
  • @Holt yes, there can be this sort of cyclic dependencies. About the data size, there is about 1000 items so efficiency quite matters. Thanks for your idea about B&B. It look promising. I will try it and report the results here later. – Paddy Xu Aug 12 '16 at 14:54
  • @Holt Thanks for your suggestion. I have tried B&B with modified lower- and upper-bound calculation, and it works perfectly. Could you write a answer below so I mark your idea as the accepted answer? – Paddy Xu Aug 17 '16 at 21:12
  • 1
    @PaddyXu Write your own answer and explain the upper/lower bound calculation and mark it as accepted, it will be a better answer that mine simply saying *"Try a custom B&B."* ;) – Holt Aug 17 '16 at 21:13

3 Answers3

5

Could you not have items a, b, c, bc, d and e? Possibly with a constraint that b and bc can't be both in the knapsack and similarly so with c and bc? My understanding is that that would be a correct solution since any solution that has b and c can be improved by substituting both by bc (by definition). The constraints on membership should take care of any other cases.

Jakub Hampl
  • 39,863
  • 10
  • 77
  • 106
  • 3
    This will be pretty inefficient and intractable as soon as the number of items starts growthing if you have dependency between all items. In an example with a, b, c, d, e, you would have to create ab, ac, ad, ae, bc, bd, be, cd, ce, de, but also abc (because, what if you put a, b and c in the knapsack?) and all triplets, and quadruplets, and... Basically, you are going to create an item for all solutions. – Holt Aug 12 '16 at 11:34
  • @Holt perhaps, but many of these will be dominated easily, so you can remove them from initial considerations relatively cheaply. – Jakub Hampl Aug 12 '16 at 14:38
  • Thanks for your answer. However this idea may not work correctly when the algorithm (any algorithm, for example DP) select both `b` and `bc`. In this case, because selecting `bc` is equal to selecting `b`, and the weight of `b` will become `0`, the dependency still exist. – Paddy Xu Aug 12 '16 at 14:51
2

This is a very interesting problem and I have been working on this for a while. The first thing to consider is that binary knapsack problem with dependent item weights/value is not trivial at all. You may consider using Bayesian networks, Markov models, and other similar techniques for solving this problem. Nonetheless, any practical approach to this problem has to make some assumptions either about the optimization model or its input. Here is an example of formulating the binary knapsack problem with value-dependent items. https://arxiv.org/pdf/1702.06662.pdf

In this work, authors have proposed modeling the input (value-related dependencies) using fuzzy graphs and then using the proposed integer linear programming model to solve the optimization problem. An extended version of the work has been accepted for publication and will be soon available online.

Please do not hesitate to contact me if you needed further information. I can also provide you with the source code of the model if needed.

Davoud Mougouei
  • 21
  • 1
2

In the end I managed to solve the problem with the B&B method proposed by @Holt. Here is the key settings:

(0) Before running the B&B algorithm, group all items depend on their dependency. All items in one partition have weight dependency with all other items in the same group, but not with items in other groups.

Settings for B&B:

(1) Upper-bound: assume that the current item has the minimum weight, i.e. assume all dependencies exist.

(2) Lower-bound: assume that the current item has the maximum weight, i.e. assume all dependencies do not exist.

(3) Current weight: Calculate the real current weight.

All the above calculations can be done in a linear time by playing around with the groups we get in step 0. Specifically, when obtaining those weights, scanning only items in current group (the group which the current item be in) is enough - items in other groups have no dependencies with the current one, so it will not change the real weight of current item.

Paddy Xu
  • 518
  • 4
  • 8