0-1 Knapsack problem with item discounts

Question

I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included below.

Simple Statement of the Problem

Suppose you have values and weights for items, such that groups of $2$ and $3$ of items in your set may produce values that are less than they would be if chosen individually (think 50% off coupons, or something similar). In this sense, we wish to find the best combination of items that allows us to carry the most weight in our knapsack, given a value constraint. How can we modify the dynamic programming method to come up with a new solution? Is a metaheuristic approach the best way? is this problem already well studied?

A mathematical statement is given below, to the best of my ability.

Let $V_1 = \{v_1, v_2, ..., v_N\}$ be the values of the single items, $V_2 = \{ r_{(1,2)}, v_{(1,3)}, ... \}$ as set of size $M$ of the values of the groups of two items , and $V_3 = \{s_{(1,2,3)}, s_{(1,2,4)} ... \}$ be as set of size $L$ of the values of the groups of three items, along with corresponding weights (with similar notation for elements) $W_1, W_2, W_3$.

We seek to find $\textbf{x} = (x_i, x_{i,j}, x_{i,j,k})$ where $x_i, x_{i,j}, x_{i,j,k} = \{0,1\}$ that is a vector of length $N + M + L$ so that

$$max\left(\sum_{w \in W_1} wx_i + \sum_{w \in W_2} wx_{i,j} + \sum_{w \in W_3}wx_{i,j,k} \right)$$ subject to $$\sum_{v \in V_1} vx_i + \sum_{v \in V_2} vx_{i,j} + \sum_{v \in V_3}vx_{i,j,k} \leq C$$

Where $C$ is the value constraint. Here, the index $(i,j)$ and $(i,j,k)$ simply correspond to the indices of their corresponding items. This also implies that an item chosen in a group of $2$ or $3$ can no longer be chosen elsewhere, so we impose the following conditions:

If $x_{i,j,k} = 1$ then $x_i = 0$, $x_j = 0$, $x_k = 0$, $x_{i,j} = 0$, $x_{i,k} = 0$, and $x_{j,k} = 0$.

If $x_{i,j} = 1$ then $x_i = 0$, $x_k = 0$, and any triplet containing item with index $i$ and $j$ is zero.

If $x_i = 1$, then any group containing item with index $i$ is zero.

Some discussion

An item in the above problem can only be discounted in a group of two, however there may be groups of 3 that produce overlap between two groups of two, hence the need to include them. This means an obvious greedy algorithm appears by ordering the greatest weights per value of triplets, choosing form there and moving on to doubles, then singles until not possible.

I want to believe a modification to the dynamic programming algorithm is possible by simply adding more rows that represent the groups of items, but I'm not sure how we would handle the "this group has been chosen, so all subsets in the group must not be chosen." condition. In my real world problem there were 150 items, which makes it seem like the dynamic programming method was not possible (there were many possible groups of 2 and 3 if you consider how big 150 choose 3 is..). In fact, the number of rows for my case would be, at first glance, $150$ $+$ ${150}\choose{2} $ + ${150}\choose{3}$ $= 562,625$ rows! Combining this with the columns representing the values which could be many, a sparse matrix option might need to be used to optimize finding a solution.

A Quick Example

Let $4$ items have values $v_1 = 4$, $v_2 = 7$, $v_3 = 3$, and $v_4 = 9$ Such that the values of the following groups have discounts: $(v_1, v_2) = 8$, $(v_2, v_4) = 14$, and $(v_1, v_2, v_4) = 15$. It is worth noting any item combinations not listed with a discount are simply the sum of their values, and do not need to be written out. Suppose further that $C = 17$.

Their weights are $w_1 = 2$, $w_2 = 5$, $w_3 = 5$, and $w_4 = 3$. Then we wish to find $\bf{x}$ so that

$$max(2x_1 + 5x_2 + 5x_3 + 3x_4 + 7x_{(1,2)} + 8x_{(2,4)} + 10x_{(1,2,4)})$$ subject to $$4x_1 + 7x_2 + 3x_3 + 9x_4 + 8x_{(1,2)} + 14x_{(2,4)} + 15x_{(1,2,4)} \leq 17$$

Where, if any item chosen is contained in another item's group, that $x$ value must be zero, to avoid overlap. It appears to me that the items with indices $\{(1,2), 3 \}$ is the solution with weight 12 with value 11.

Answer 1

The problem is NP-hard, by a reduction from 3-dimensional matching. For each triplet $(x,y,z)$ in the 3-dimensional matching problem, we have items $x_1$, $y_2$, $z_3$ and set the group of 3 items $(x_1,y_2,z_3)$ to have value $1$ and weight 0. Each individual item has value $0$ and weight $+\infty$. Now the solution to your knapsack problem yields a solution to the original 3-dimensional matching problem. 3-dimensional matching is strongly NP-hard, so there is no pseudo-polynomial-time algorithm for it (unless P = NP).

If you don't allow triplets and only allow pairs, I don't know whether the problem can be solved in pseudo-polynomial time. It looks like a hybrid between a knapsack problem and maximum matching. Form a graph with one vertex per item. Each pair corresponds to an edge in this graph. Add a special vertex $s$; each individual item corresponds to an edge between that item and $s$. Now you can annotate each edge with a value and weight, and the goal is to find a matching whose total weight does not exceed the capacity, and whose total value is maximized. I don't know if there is a pseudo-polynomial-time algorithm for this problem. It certainly can't be solved in polynomial time (unless P = NP), as it is at least as hard as the usual knapsack problem, which is NP-hard.