装箱问题：不按顺序选择箱

Question

我正在研究一个简单的装箱问题，我意识到求解器正在选择最佳数量的箱子来包装物品，但是，箱子不是连续的。

以下是我的程序：

from ortools.linear_solver import pywraplp

s = pywraplp.Solver("", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

num_bins = 10
num_items = 10
c = 10
w = [1, 2, 3, 4, 5, 1, 3, 3, 4, 2]


x = {}
for i in range(num_items):
    for j in range(num_bins):
        x[i, j] = s.BoolVar("")

y = {}
for i in range(num_bins):
    y[i] = s.BoolVar("")

# minimize the number of bins used
obj = sum(y[j] for j in range(num_bins))

# pack each item in exactly one bin
for i in range(num_items):
    s.Add(sum(x[i, j] for j in range(num_bins)) == 1)

# bin capacity constraint
for j in range(num_bins):
    s.Add(sum(w[i] * x[i, j] for i in range(num_items)) <= c * y[j])

# solve
s.Minimize(obj)
s.Solve()

bin_for_item = [-1 for i in range(num_items)]

for i in range(num_items):
    for j in range(num_bins):
        if x[i, j].SolutionValue() > 0.5:
            bin_for_item[i] = j

print(f"number of bins = {s.Objective().Value()}")
print(f"Bin assignment for each item: {bin_for_item}")

Solver 将物品打包到由

[7, 7, 2, 7, 5, 2, 5, 7, 2, 2]

索引的箱子中

谨慎挑选编号为

0, 1, 2

的垃圾箱

Answer 1

您可以（并且应该）强制执行垃圾箱的使用顺序，只有当垃圾箱

i+1

已被使用时才允许使用垃圾箱

i

。这是因为所有的垃圾箱都无法区分。

这些被称为对称破坏约束，通常它们是多余的，但它们在某些条件下可以帮助求解器。

附加约束：

for i in range(num_bins - 1):
    s.Add(y[i + 1] <= y[i])

现在，bins的选择如下：

[0, 2, 2, 1, 0, 0, 1, 0, 2, 1]

。 因此，只使用前 3 个 bin，这就是我们想要的行为