5
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ This is known as the Quadratic Knapsack problem. This problem has been widely studied. In case you're interested, some dedicated algorithms are available online, for example here hjemmesider.diku.dk/~pisinger/codes.html $\endgroup$
    – fontanf
    Apr 4, 2022 at 15:27

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Interesting idea! Do you happen to have a reference to the Bill Cook example you gave? I'm curious to see how fast your suggested approach converges, as the initial relaxation might significantly over-approximate the final objective (it does help that the knapsack can only hold 12 items). $\endgroup$ Apr 4, 2022 at 18:44
  • $\begingroup$ From an implementation perspective, do you have a recommendation on how to implement the simultaneous column and row generation efficiently? Would you simply solve the IP problem with relaxed objective to optimality, add any of the $z_{ij}$ vars and constraints, and resolve, or would you do something more sophisticated? $\endgroup$ Apr 4, 2022 at 18:49
  • 1
    $\begingroup$ @JorisKinable Cook mentions his approach here: math.uwaterloo.ca/tsp/pubs $\endgroup$
    – RobPratt
    Apr 4, 2022 at 18:54
  • 1
    $\begingroup$ @JorisKinable Yes, what you suggested is what I would try first. A more sophisticated approach would be to use a "one-tree" implementation. $\endgroup$
    – RobPratt
    Apr 4, 2022 at 18:56
  • $\begingroup$ @JorisKinable I suspect the performance will strongly depend on the relative sizes of the bonuses, both with respect to the weights and with respect to each other. As an extreme case, if all bonuses are equal, the process converges in one step. $\endgroup$
    – RobPratt
    Apr 4, 2022 at 19:03
3
$\begingroup$

Pyomo code 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$

Pareto optima front

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.