MCKP (multiple-choice knapsack problem) with many items

Answered

Fabio David

March 29, 2023 23:04

• 
• 
• 

Hi,
I have a problem that can be modeled as a MCKP (multiple-choice knapsack problem). It is possible to calculate all items i in advance (python script) and classify them in C classes. Each item is assigned a value p.

I have a multi-objective function: first, I want to maximize the number of selected items, limited to one item per class, then I want to maximize the total value in the knapsack. I am not required to select an item from all classes. So far, so good. The problem worsens because I have some constraints to avoid incompatibilities between items.

The formulation is actually quite simple. However, each class C may contain thousands items, if not hundreds of thousands. It takes forever to find a solution, even if I reduce the number of items per class. I believe that the incompatibilities constraints contribute significantly to the difficulty in finding a solution.

Do you have any recommendations for improving performance? How do you suggest to formulate this model?

Thanks in advance,
Fabio

Related to

• Formulation

0

• 

  David Torres Sanchez

  • Gurobi Staff

  March 30, 2023 09:10 Edited

  Hi Fabio,

  What objective is getting stuck? Both or just the second one?
  As you say the problem may become much harder from the constraints that avoid incompatibilities between items. I am imagining many constraints like \(x_{ic} + x_{jc} \leq 1\) (for a pair items in an incompatible set \((i,j)\in I\) and class \(c\)).

  Some things come to mind that you can try:

  • Adding these constraints as Lazy (either in a callback or by setting the Lazy attribute to 1, 2 or 3).
  • I am not sure about this but maybe multi-objective presolve is a bit limiting, could you try to solve the problem without this to see if this helps? (Also, try this with the Lazy constraints).
  • Try and come up with a stronger version of the incompatibility constraints, e.g. combine all incompatible items into a single constraint \(x_{ic} + \sum_{(i,j)\in I} x_{jc} \leq 1, \forall i\)
  • Reformulate the incompatible sets using indicator constraints (Model.addGenConstrIndicator()). e.g. \(\texttt{model.addConstrs(((x[i,c] == 1) >> (x[j,c] == 0) for (i,j) in I for c in C))}\) and the converse.

  
  Cheers, 
  David

  0
• 

  Fabio David

  May 15, 2023 13:33

  • 
  • 
  • 

  Sorry for the long response time. I followed all the suggestions, but it didn't achieve much better results. I decided to change my approach.
  
  Anyway, I really appreciate your suggestions, as they have been very helpful in my understanding and utilization of Gurobi.
  
  Thanks,
  Fabio

  0

Please sign in to leave a comment.