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.
- My knapsack can hold a dozen items
- There are thousands of items to choose from
- 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?