约束相同值的背包

Question

我正在解决 python 中的多个背包问题：

问题是将物品的一个子集打包到五个箱子中，每个箱子的最大容量为 100，因此总的打包值是最大值。

data = {}
data['weights'] = [
    48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36
]
data['values'] = [
    10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25
]
assert len(data['weights']) == len(data['values'])
data['num_items'] = len(data['weights'])
data['all_items'] = range(data['num_items'])

data['bin_capacities'] = [100, 100, 100, 100, 100]
data['num_bins'] = len(data['bin_capacities'])
data['all_bins'] = range(data['num_bins'])

数据包括以下内容：

权重：包含项目权重的向量。值：包含项目值的向量。 capacity：包含 bin 容量的向量。

以下代码声明了 MIP 求解器。

solver = pywraplp.Solver.CreateSolver('SCIP')
if solver is None:
    print('SCIP solver unavailable.')
    return

以下代码为问题创建了变量。

# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in data['all_items']:
    for b in data['all_bins']:
        x[i, b] = solver.BoolVar(f'x_{i}_{b}')

以下代码定义了问题的约束条件：

Each x[(i, j)] is a 0-1 variable, where i is an item and j is a bin. In the solution, x[(i, j)] will be 1 if item i is placed in bin j, and 0 otherwise.

# Each item is assigned to at most one bin.
for i in data['all_items']:
    solver.Add(sum(x[i, b] for b in data['all_bins']) <= 1)

# The amount packed in each bin cannot exceed its capacity.
for b in data['all_bins']:
    solver.Add(
        sum(x[i, b] * data['weights'][i]
            for i in data['all_items']) <= data['bin_capacities'][b])



# Maximize total value of packed items.
objective = solver.Objective()
for i in data['all_items']:
    for b in data['all_bins']:
        objective.SetCoefficient(x[i, b], data['values'][i])
objective.SetMaximization()

我尝试添加另一个约束，即同一包中的所有物品都应具有相同的重量，但我很难在 python 中做到这一点。你能帮我编码吗？

谢谢

Answer 1

只是一个草图。考虑一下...也许修复它（这只是一个想法）。

你有什么：赋值矩阵 A 项 <-> bins

item     0   1   2   3   4   5   6   7   8   9   10   11   12   13   14
   0
   1
   2
   3
   4 
        <=1 <=1 <=1 ...
  bin

你应该添加什么：Assignment-matrix B item-classes <-> bins

物品-class：一组相同重量的所有物品

例如：

import numpy as np
weights = np.array([48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36])
unique_weights = set(weights)
partition = [np.where(weights == i)[0] for i in unique_weights]

# [array([ 3,  4,  8, 13, 14]), array([ 2,  6,  7, 12]), array([0, 5]), array([9]), array([ 1, 10, 11])]

附加赋值矩阵：

item-class    0   1   2   3   4 
   0                             <=1
   1                             <=1
   2                             <=1
   3                             <=1
   4                             <=1
  bin

然后：Link/Channel那些

如果 class C 没有唯一分配给此 bin，则分配给 class C 的 bin 的项目总和为 0，否则为无界（big-M）。

类似于：

for b in range(n_bins):
    for c in range(n_partitions):
        sum(A[b, all_indices_of_items_in_class(c)]) <= B[b, c] * len(all_indices_of_items_in_class(c))

备注

显然，这更多是对现状的补充。

不将 A 建模为大布尔垫可能更有意义，而只是引入基数约束（选择了多少相同的项目），因为我们已经有了表示我们选择“什么”的变量。

约束相同值的背包

Knapsack with constraint same value

python

optimization

knapsack-problem

你有什么：赋值矩阵 A 项 <-> bins

你应该添加什么：Assignment-matrix B item-classes <-> bins

然后：Link/Channel那些

备注