箱包/背包优化问题设计

Question

我有一个场景，我需要一些帮助来制定问题，这样我才能正确地实施优化方法。我希望有人能给我一些指导，表面上看起来很简单，但我很难弄清楚如何正确编码变量、约束等。

情况是这样的：

• 需要将多个物品放入箱子/背包中

例：

每个项目有两个值的向量：

项目=[[7,6]，[14,2]，[27,23]，[5,15]]

箱子/背包的向量，第一个值为物品第一个值可接受的上限。第二个值相同，但适用于箱子/背包中每个物品的第二个值。第三个值是箱子/背包可以容纳的最大物品数。最后一个值是箱子/背包的价格/成本。

双选项=[[64000145035022000]，[8000450,648000]]

目标是以最有效的方式包装所有物品，以提供最低成本（使用箱子/背包的价格）。

我在考虑两种解决问题的方法：

• 使用MILP方法的OR-工具
• 带有背包求解器的OR-工具

我不一定会被OR-Tools卡住，它只是我一直在玩的东西，从我看到的报告来看，它似乎在不同的语言之间运行得很好。如果能够对此建模，然后在以后选择一种语言，那就太好了。

有一件事可能不太明显，那就是可用垃圾箱品种的数量会发生变化。有时我会有两三个可供选择，有时会更多，可能多达一百个。要打包的来料数量也会根据日期而变化。

如果有人能为解决这个问题提供一些指导，我将不胜感激。

干杯

青蛙

Answer 1

我建议使用装箱示例作为这个问题的模板。它使用SCIP求解器。

 solver = pywraplp.Solver.CreateSolver('SCIP')

在该示例中，目标是尽量减少用于包装所有物品的箱子数量。我认为这适用于你的情况，尤其是在箱子数量未知的情况下。显然，对于n个项目，所需的最大箱子数量为n，因为最大数量的箱子将导致一个项目被放置在自己的箱子中。

#> Constraints:
## Each item must be packed once
for i in data['items']:
    solver.Add(sum(x[i, j] for j in data['bins']) == 1)

## The sum of each weight type cannot exceed the capacity for that bin
## You have two weight types, k.
for k in range(2):
    for j in data['bins']:
        solver.Add(
            sum(x[(i, j)] * data['weights'][k][i] for i in data['items']) <= y[j] *
            data['bin_capacity'][k])

## The number of items cannot exceed the numerical capacity of each bin
## Let's assume this capacity is element 2 of data['bin_capacities']
for j in data['bins']:
    solver.Add(
        sum(x[(i, j)] for i in data['items']) <= y[j] * data['bin_capacity'][2])

#> Objective:
## The original objective function used in the example.
solver.Minimize(solver.Sum([y[j] for j in data['bins']]))

## With the addition of a variable cost for a bin, you may need the following.
solver.Minimize(solver.Sum([y[j] * data['bin_cost'] for j in data['bins']]))

Answer 2

背包解算器不能解决你的问题，因为它是一个纯1背包解算器。

您可以使用MILP求解器或CP-SAT。