MCKP (multiple-choice knapsack problem) with many items

回答済み

Fabio David

2023年03月29日 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

関連

• Formulation

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:46

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  David Torres Sanchez

  • Gurobi Staff

  2023年03月30日 09:10 編集済み

  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

  2023年05月15日 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

投稿コメントは受け付けていません。