Solving multi-dimensional knapsack problems.

回答済み

Travis Dart

• 2024年11月21日 02:55
• 編集済み

I have a knapsack problem of sorts. I'm trying to find what combinations of foods combine to satisfy a person's nutritional requirements. I have a list of ~1,200 foods from the USDA and am trying to satisfy 29 nutritional requirements. So, I want to know what combinations of 1,200, 29-dimensional objects fit into a 29-dimensional knapsack.

I've tried really hard with an open-source solver (OR-Tools) and have gotten maybe 75 solutions. I was able to contort the solver into computing all solutions, but is infeasibly slow and would take 2+ years to complete. My code is available on GitHub (the solver bit is here).

I'm thinking maybe I should use a better solver like Gurobi, but I wanted to get opinions on two questions:

• Will using Gurobi instead of OR-Tools make that much of a difference, or would you suspect this just an infeasibly-large problem?

• For a problem like this, can Gurobi return all solutions, or is the solver "optimizing" in the sense that it just returns a small "optimal" set of solutions? (This has been an issue with my current solver.)

Thanks.

関連

• Solutions

1

• 

  Ryuta Tamura

  Gurobi Staff

  • 2024年11月21日 15:19
  • 編集済み

  Hi,

  If I understand correctly, you are interested in enumerating "all" feasible solutions. In such use case, SolutionPool feature and PoolSearchMode parameter might help. By setting PoolSearchMode to 2, Gurobi will search n-best solutions. If n is large enough, all feasible solutions can be found.
  However, please note that the number of feasible solutions of MIP easily divergent. Hence, enumerating all solutions may not be possible in practice. In fact, the number of combinations of p foods can be \( O(2^p) \), and in your case \( 2^{1200}\)!! Of course, this reduced by the constraint, but this value exceeds the maximum value of the signed integer \( 2^{31}-1\).

  Thanks,
  Ryuta

  0

サインインしてコメントを残してください。