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

$$maxleft(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.