Knapsack - How to optimize bonuses for each pair of items

Question

I am trying to solve a variation of the knapsack problem where every pair of items in my knapsack has a bonus or penalty associated with it.

1. My knapsack can hold a dozen items
2. There are thousands of items to choose from
3. Every pair of items has a known bonus or penalty associated with it

What I've tried is to create a binary variable for every pair of items which represents the logical AND of whether the pair belongs to the solution. My objective function then maximizes the total weight in the knapsack along with sum of the bonuses. The issue I'm running into is that having thousands of items creates a lot of these logical-AND helper variables and is very slow to run. Is there a better way to model this problem?

Answer 1

One approach is to introduce the pairs dynamically only when needed. Initially, solve a relaxation where every pair yields the highest bonus. (Note: I am suggesting to relax the objective and not to relax integrality.) For the resulting optimal solution, compute the true objective value. If it matches the solver’s claimed objective value, you are done. Otherwise, introduce the variables and constraints for any newly arising pairs, and repeat until the upper bound from the relaxation matches the lower bound from the incumbent. This idea is similar to one Bill Cook has used to solve TSP instances where the true edge cost is obtained by a Google Maps query but initially approximated by a great-circle lower bound.

---

More explicitly, let $w_i$ be the weight of item $i$, and let $b_{ij}$ be the bonus or penalty for pair $(i,j)$ with $i<j$. Let binary decision variable $x_i$ indicate whether item $i$ is chosen. The original (quadratic knapsack) problem is to maximize $\sum_i w_i x_i + \sum_{i<j} b_{ij} x_i x_j$ subject to $\sum_i x_i \le 12$. For small enough instances, you can solve the problem directly via MIQP, by linearizing in the usual way, or by using Glover's linearization.

Here are more details of the indirect approach I sketched earlier. Let $M=\max_{i<j} b_{ij}$ be the maximum bonus among all pairs. Assume for the moment that it is optimal to choose exactly $12$ items. My suggested reformulation is to introduce binary (or just nonnegative) decision variable $z_{ij}$ and maximize $$\sum_i w_i x_i + \binom{12}{2}M + \sum_{i<j} (b_{ij}-M) z_{ij} \tag1$$ subject to \begin{align} \sum_i x_i &= 12 \tag2 \\ x_i + x_j - 1 &\le z_{ij} &&\text{for $i<j$} \tag3 \end{align} But introduce $z_{ij}$ and constraint $(3)$ dynamically only as needed.

If instead it might be optimal to choose fewer than $12$ items, let binary decision variable $y_k$ indicate whether $k$ items are chosen and maximize $$\sum_i w_i x_i + \sum_{k=0}^{12} \binom{k}{2}M y_k + \sum_{i<j} (b_{ij}-M) z_{ij} \tag4$$ subject to \begin{align} \sum_i x_i &= \sum_{k=0}^{12} k y_k \tag5 \\ \sum_{k=0}^{12} y_k &=1 \tag6 \\ x_i + x_j - 1 &\le z_{ij} &&\text{for $i<j$} \tag7 \end{align} Now introduce $z_{ij}$ and constraint $(7)$ dynamically only as needed.

Answer 2

Pyomo code

you do need a matrix for the value of each pair of items model.V[i,j] you also need a vector for the weight of each item model.W[i] I have created them randomly as follows:

df=pd.DataFrame()

N=50
df['w']=[random.random() for i in range(N)]
df
dic={}
for i in range(1,1+N):
    for j in range(1,1+N):
        if i>j:
            dic[i,j]= 0.5-random.random()
            dic[j,i]=dic[i,j]
        if i==j:
            dic[i,j]=0

Now the formulation will be a classic multiobjective optimization $x_i$ is a binary variable representing select or not $Z_{i,j}$ is a real variable represinting $x_i*x_j$

$\max_{x_i} OF_1$

$OF_1= \sum_{i,j} V_{i,j}Z_{i,j}$

$OF_2= \sum_i w_ix_i$

$Z_{i,j} \leq x_i \ \ \forall i\ne j $

$Z_{i,j} \leq x_j \ \ \forall i\ne j $

$Z_{i,j} \geq x_i+x_j-1 \ \ \forall i\ne j $

$OF_2 \geq \epsilon$

$ \sum_i x_i=12$