多个背包的优化问题不能正常工作
Optimization problem with multiple knapsack does not work correctly
我正在尝试解决 Python 中的多个背包问题，该问题包括将物品放入 5 个箱子中，约束条件是每个箱子（包）必须包含具有相同簇的物品（因此我们不能找到同一箱子中具有不同簇的两个对象）并最大化箱子中包装的物品的总和 KPI
这是数据帧数据：
index Cluster PageId OsId BrowserId Impressions VideoComplete Clicks VolumePred KPIPred ConversionPred pond
0 1 0 1016529 11 16 43 16 1 175.0 0.025703 1
1 2 0 1016529 11 17 1 1 0 4.0 0.100000 1
2 12 0 1068379 11 12 1 0 0 4.0 0.150000 1
3 21 0 1074581 11 16 82 36 2 334.0 0.024457 1
4 22 0 1074581 12 14 3 2 0 12.0 0.035648 1
... ... ... ... ... ... ... ... ... ... ... ... ...
310 1392 9 955767 11 11 264 170 12 1076.0 0.056217 1
311 1396 9 955767 11 17 42 32 2 171.0 0.118330 1
312 1397 9 955767 12 12 7 1 2 29.0 0.234646 1
313 1398 9 955767 12 14 31 17 1 126.0 0.026832 1
314 1405 9 988119 11 16 66 49 1 269.0 0.019075 1
求解：
我创建了第一个赋值矩阵 A：items <-> bins like this :
item 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
bins
0
1
2
3
4
<=1 <=1 <=1 ................................... <=1 <=1 <=1
data1 = {}
pond = data['pond']
Cluster = data['Cluster']
OsId = data['OsId']
BrowserId = data['BrowserId']
PageId = data['PageId']
volume = data['VolumePred']
conversion = data['ConversionPred']
KPI = data['KPIPred']
assert len(OsId) == len(BrowserId) == len(PageId) == len(conversion)
data1['Cluster'] = Cluster
data1['pond'] = pond
data1['OsId'] = OsId
data1['BrowserId'] = BrowserId
data1['PageId'] = PageId
data1['conversion'] = conversion
data1['volume'] = volume
data1['KPI'] = KPI
data1['items'] = list(range(len(BrowserId)))
data1['num_items'] = len(OsId)
number_bags = 5 #All have the same capacity of 50 pounds
data1['bag_capacities'] = [50,50,50,50,50]#pounds
data1['bag_PageId'] = [50,50,50,50,50] #while this equals bag_capacities, I made it its own variable in case
data1['conversion_capacities'] = [5,5,5,5,5]
#data1['bag_capacities'] = [50,50,50,50,50] #while this equals bag_capacities, I made it its own variable in case
#I wanted to change the OsId at a later data1
data1['bags'] = list(range(number_bags))
assert len(data1['bag_capacities']) == number_bags
assert len(data1['bag_capacities']) == len(data1['bag_PageId']) == len(data1['conversion_capacities'])
print("OsId: ",*data1['OsId'])
print('BrowserId:',*data1['BrowserId'])
print('PageId:',*data1['PageId'])
print('conversioniation Levels:', *data1['conversion'])
print("Number of Items:", data1['num_items'])
print("Number of Knapsacks:" , number_bags)
print('Knapsack Capacities: 50 Pounds, 50 cubic inches, 5 Levels of conversioniation')
变量 1
#x[i,j] for item i in knapsack j
x = {}
for i in data1['items']:
for j in data1['bags']:
x[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))
然后，我添加第二个矩阵：Assignment-matrix B item-类 <-> bins:
data2={}
unique_cluster = set(np.array(Cluster))
partition = [np.where(Cluster == i)[0] for i in unique_cluster]
data2['class'] = list(unique_cluster)
data2['bags'] = list(range(number_bags))
#x[i,j] for item i in knapsack j
x2 = {}
for i in data2['class']:
for j in data2['bags']:
x2[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))
然后，我确定约束列表：
#Constraint for an item being placed in 1 knapsack
for i in data1['items']:
solver.Add(sum(x[i,j] for j in data1['bags'])<=1)
#Knapsack Capacity Constraint
for j in data1['bags']:
solver.Add(sum(x[(i,j)]*data1['pond'][i]
for i in data1['items']) == 5)
#Constraint for a class of item is being placed in 1 knapsack
for i in data2['class']:
solver.Add(sum(x2[i,j] for j in data2['bags'])<=1)
A=np.where(Cluster == 0)[0].tolist()
for b in data1['bags']:
for c in data2['class']:
print(b,c)
u=len(np.where(Cluster == c)[0].tolist())
print(c,b)
solver.Add(sum(x[z,b]
for z in np.where(Cluster == c)[0].tolist()) <= (x2[c,b]*u))
然后，我精确优化 objective:
objective = solver.Objective()
for i in data1['items']:
for j in data1['bags']:
objective.SetCoefficient(x[(i,j)], data1['KPI'][i])
objective.SetMaximization()
分辨率
solv = solver.Solve()
if solv == pywraplp.Solver.OPTIMAL:
#print('Total Packed Value:', objective.Value())
total = 0
kpi_moyen = 0
kpi=0
total_conversion = 0
nombre_impression = 5
for j in data1['bags']:
bag_value = 0
bag_weight = 0
bag_volume= 0
bag_rad = 0
bag_conversion=0
max = 0
i_max=0
print('\n','Bag', j+1 , '\n')
for i in data1['items']:
if((x[i,j].solution_value()>0)):
print('OsId',data1['OsId'][i],
'Cluster', data1['Cluster'][i],
'BrowserId', data1['BrowserId'][i],
'PageId', data1['PageId'][i],
'conversion', data1['conversion'][i],
'volume', data1['volume'][i],
'KPI', data1['KPI'][i]
)
bag_value += data1['volume'][i]
print(bag_value)
bag_weight += data1['KPI'][i]
bag_conversion += data1['conversion'][i]
print('Packed Knapsack Volume Value: ', bag_value)
print('impression number', nombre_impression)
print('Packed Knapsack KPI: ', bag_weight/nombre_impression)
kpi = bag_weight/nombre_impression
total= total+bag_value
kpi_moyen = kpi_moyen+kpi
total_conversion= total_conversion+bag_conversion
print("#######################################################")
print("#######################################################")
print("#######################################################")
print("Le volume total", total)
print("KPI Moyen", kpi_moyen/5)
else:
print("There is no optimal solution")
最后我得到了这五个装有物品的箱子：
> Bag 1
>
> OsId 11 Cluster 0 BrowserId 12 PageId 1149586 conversion 3.0 volume
> 4.0 KPI 0.6890546435965691
> 4.0
OsId 99 Cluster 0 BrowserId 16 PageId 1154705 conversion 3.0 volume 8.0 KPI 0.3472222222222222
> 12.0
OsId 11 Cluster 0 BrowserId 17 PageId 789615 conversion 3.0 volume 4.0 KPI 0.6564351851851853
> 16.0
OsId 11 Cluster 0 BrowserId 11 PageId 955761 conversion 9.0 volume 37.0 KPI 0.2541666666666666
> 53.0
OsId 99 Cluster 7 BrowserId 16 PageId 917224 conversion 4.0 volume 12.0 KPI 0.3292739040060469
> 65.0 Packed Knapsack Volume Value: 65.0 impression number 5 Packed Knapsack KPI: 0.45523052433533806
>
> Bag 2
>
> OsId 99 Cluster 12 BrowserId 16 PageId 941080 conversion 2.0 volume
> 4.0 KPI 0.5508680555555555
> 4.0
OsId 12 Cluster 9 BrowserId 16 PageId 1018637 conversion 4.0 volume 12.0 KPI 0.321111111111111
> 16.0
OsId 11 Cluster 9 BrowserId 17 PageId 1154705 conversion 13.0 volume 33.0 KPI 0.3886526452221044
> 49.0
OsId 99 Cluster 9 BrowserId 12 PageId 955761 conversion 11.0 volume 33.0 KPI 0.3366657218442933
> 82.0
OsId 12 Cluster 9 BrowserId 12 PageId 955767 conversion 7.0 volume 29.0 KPI 0.2346455795175744
> 111.0 Packed Knapsack Volume Value: 111.0 impression number 5 Packed Knapsack KPI: 0.3663886226501277
>
> Bag 3
>
> OsId 99 Cluster 4 BrowserId 16 PageId 1109643 conversion 1.0 volume
> 4.0 KPI 0.3055555555555556
> 4.0
OsId 11 Cluster 4 BrowserId 11 PageId 1149586 conversion 6.0 volume 8.0 KPI 0.7676237922705315
> 12.0
OsId 11 Cluster 4 BrowserId 15 PageId 1149586 conversion 8.0 volume 33.0 KPI 0.2383133975812547
> 45.0
OsId 12 Cluster 4 BrowserId 16 PageId 1154705 conversion 10.0 volume 41.0 KPI 0.2528392857142857
> 86.0
OsId 12 Cluster 4 BrowserId 14 PageId 955767 conversion 4.0 volume 20.0 KPI 0.2225
> 106.0
Packed Knapsack Volume Value: 106.0 impression number 5 Packed Knapsack KPI: 0.35736640622432553
>
> Bag 4
>
> OsId 11 Cluster 15 BrowserId 17 PageId 1109643 conversion 5.0 volume
> 12.0 KPI 0.3877777777777778
> 12.0
OsId 11 Cluster 15 BrowserId 17 PageId 1187774 conversion 3.0 volume 12.0 KPI 0.236237684729064
> 24.0
OsId 11 Cluster 15 BrowserId 11 PageId 955765 conversion 10.0 volume 41.0 KPI 0.2319838228361533
> 65.0
OsId 11 Cluster 18 BrowserId 17 PageId 1074581 conversion 5.0 volume 16.0 KPI 0.300344742063492
> 81.0
OsId 11 Cluster 18 BrowserId 16 PageId 1148073 conversion 3.0 volume 4.0 KPI 0.6833333333333333
> 85.0 Packed Knapsack Volume Value: 85.0 impression number 5 Packed Knapsack KPI: 0.36793547214796407
>
> Bag 5
>
> OsId 11 Cluster 21 BrowserId 12 PageId 1016529 conversion 3.0 volume
> 8.0 KPI 0.3541076152683295
> 8.0
OsId 11 Cluster 21 BrowserId 12 PageId 1068379 conversion 3.0 volume 4.0 KPI 0.6711734693877551
> 12.0
OsId 12 Cluster 21 BrowserId 16 PageId 911433 conversion 5.0 volume 16.0 KPI 0.3160714285714284
> 28.0
OsId 11 Cluster 21 BrowserId 12 PageId 941080 conversion 2.0 volume 8.0 KPI 0.2876372053872053
> 36.0
OsId 12 Cluster 21 BrowserId 14 PageId 941080 conversion 2.0 volume 8.0 KPI 0.275
> 44.0
问题是我在同一个包或垃圾箱中发现了多个簇的物品，例如在包 1 中，我们发现了簇为 0 和 7 的物品。
我该如何解决这个问题？
您的“class 物品的约束被放置在 1 个背包中”
for i in data2['class']:
solver.Add(sum(x2[i,j] for j in data2['bags'])<=1)
确保每个 class 都放入某个背包中。不保证每个背包只能装一个class.
我想你必须添加
# Only one class per knapsack Constraint
for j in data1['bags']:
solver.Add(sum(x2[(i,j)]
for i in data2['class']) <= 1)
相反。
我正在尝试解决 Python 中的多个背包问题，该问题包括将物品放入 5 个箱子中，约束条件是每个箱子（包）必须包含具有相同簇的物品（因此我们不能找到同一箱子中具有不同簇的两个对象）并最大化箱子中包装的物品的总和 KPI
这是数据帧数据：
index Cluster PageId OsId BrowserId Impressions VideoComplete Clicks VolumePred KPIPred ConversionPred pond
0 1 0 1016529 11 16 43 16 1 175.0 0.025703 1
1 2 0 1016529 11 17 1 1 0 4.0 0.100000 1
2 12 0 1068379 11 12 1 0 0 4.0 0.150000 1
3 21 0 1074581 11 16 82 36 2 334.0 0.024457 1
4 22 0 1074581 12 14 3 2 0 12.0 0.035648 1
... ... ... ... ... ... ... ... ... ... ... ... ...
310 1392 9 955767 11 11 264 170 12 1076.0 0.056217 1
311 1396 9 955767 11 17 42 32 2 171.0 0.118330 1
312 1397 9 955767 12 12 7 1 2 29.0 0.234646 1
313 1398 9 955767 12 14 31 17 1 126.0 0.026832 1
314 1405 9 988119 11 16 66 49 1 269.0 0.019075 1
求解：
我创建了第一个赋值矩阵 A：items <-> bins like this :
item 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
bins
0
1
2
3
4
<=1 <=1 <=1 ................................... <=1 <=1 <=1
data1 = {}
pond = data['pond']
Cluster = data['Cluster']
OsId = data['OsId']
BrowserId = data['BrowserId']
PageId = data['PageId']
volume = data['VolumePred']
conversion = data['ConversionPred']
KPI = data['KPIPred']
assert len(OsId) == len(BrowserId) == len(PageId) == len(conversion)
data1['Cluster'] = Cluster
data1['pond'] = pond
data1['OsId'] = OsId
data1['BrowserId'] = BrowserId
data1['PageId'] = PageId
data1['conversion'] = conversion
data1['volume'] = volume
data1['KPI'] = KPI
data1['items'] = list(range(len(BrowserId)))
data1['num_items'] = len(OsId)
number_bags = 5 #All have the same capacity of 50 pounds
data1['bag_capacities'] = [50,50,50,50,50]#pounds
data1['bag_PageId'] = [50,50,50,50,50] #while this equals bag_capacities, I made it its own variable in case
data1['conversion_capacities'] = [5,5,5,5,5]
#data1['bag_capacities'] = [50,50,50,50,50] #while this equals bag_capacities, I made it its own variable in case
#I wanted to change the OsId at a later data1
data1['bags'] = list(range(number_bags))
assert len(data1['bag_capacities']) == number_bags
assert len(data1['bag_capacities']) == len(data1['bag_PageId']) == len(data1['conversion_capacities'])
print("OsId: ",*data1['OsId'])
print('BrowserId:',*data1['BrowserId'])
print('PageId:',*data1['PageId'])
print('conversioniation Levels:', *data1['conversion'])
print("Number of Items:", data1['num_items'])
print("Number of Knapsacks:" , number_bags)
print('Knapsack Capacities: 50 Pounds, 50 cubic inches, 5 Levels of conversioniation')
变量 1
#x[i,j] for item i in knapsack j
x = {}
for i in data1['items']:
for j in data1['bags']:
x[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))
然后，我添加第二个矩阵：Assignment-matrix B item-类 <-> bins:
data2={}
unique_cluster = set(np.array(Cluster))
partition = [np.where(Cluster == i)[0] for i in unique_cluster]
data2['class'] = list(unique_cluster)
data2['bags'] = list(range(number_bags))
#x[i,j] for item i in knapsack j
x2 = {}
for i in data2['class']:
for j in data2['bags']:
x2[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))
然后，我确定约束列表：
#Constraint for an item being placed in 1 knapsack
for i in data1['items']:
solver.Add(sum(x[i,j] for j in data1['bags'])<=1)
#Knapsack Capacity Constraint
for j in data1['bags']:
solver.Add(sum(x[(i,j)]*data1['pond'][i]
for i in data1['items']) == 5)
#Constraint for a class of item is being placed in 1 knapsack
for i in data2['class']:
solver.Add(sum(x2[i,j] for j in data2['bags'])<=1)
A=np.where(Cluster == 0)[0].tolist()
for b in data1['bags']:
for c in data2['class']:
print(b,c)
u=len(np.where(Cluster == c)[0].tolist())
print(c,b)
solver.Add(sum(x[z,b]
for z in np.where(Cluster == c)[0].tolist()) <= (x2[c,b]*u))
然后，我精确优化 objective:
objective = solver.Objective()
for i in data1['items']:
for j in data1['bags']:
objective.SetCoefficient(x[(i,j)], data1['KPI'][i])
objective.SetMaximization()
分辨率
solv = solver.Solve()
if solv == pywraplp.Solver.OPTIMAL:
#print('Total Packed Value:', objective.Value())
total = 0
kpi_moyen = 0
kpi=0
total_conversion = 0
nombre_impression = 5
for j in data1['bags']:
bag_value = 0
bag_weight = 0
bag_volume= 0
bag_rad = 0
bag_conversion=0
max = 0
i_max=0
print('\n','Bag', j+1 , '\n')
for i in data1['items']:
if((x[i,j].solution_value()>0)):
print('OsId',data1['OsId'][i],
'Cluster', data1['Cluster'][i],
'BrowserId', data1['BrowserId'][i],
'PageId', data1['PageId'][i],
'conversion', data1['conversion'][i],
'volume', data1['volume'][i],
'KPI', data1['KPI'][i]
)
bag_value += data1['volume'][i]
print(bag_value)
bag_weight += data1['KPI'][i]
bag_conversion += data1['conversion'][i]
print('Packed Knapsack Volume Value: ', bag_value)
print('impression number', nombre_impression)
print('Packed Knapsack KPI: ', bag_weight/nombre_impression)
kpi = bag_weight/nombre_impression
total= total+bag_value
kpi_moyen = kpi_moyen+kpi
total_conversion= total_conversion+bag_conversion
print("#######################################################")
print("#######################################################")
print("#######################################################")
print("Le volume total", total)
print("KPI Moyen", kpi_moyen/5)
else:
print("There is no optimal solution")
最后我得到了这五个装有物品的箱子：
> Bag 1
>
> OsId 11 Cluster 0 BrowserId 12 PageId 1149586 conversion 3.0 volume
> 4.0 KPI 0.6890546435965691
> 4.0
OsId 99 Cluster 0 BrowserId 16 PageId 1154705 conversion 3.0 volume 8.0 KPI 0.3472222222222222
> 12.0
OsId 11 Cluster 0 BrowserId 17 PageId 789615 conversion 3.0 volume 4.0 KPI 0.6564351851851853
> 16.0
OsId 11 Cluster 0 BrowserId 11 PageId 955761 conversion 9.0 volume 37.0 KPI 0.2541666666666666
> 53.0
OsId 99 Cluster 7 BrowserId 16 PageId 917224 conversion 4.0 volume 12.0 KPI 0.3292739040060469
> 65.0 Packed Knapsack Volume Value: 65.0 impression number 5 Packed Knapsack KPI: 0.45523052433533806
>
> Bag 2
>
> OsId 99 Cluster 12 BrowserId 16 PageId 941080 conversion 2.0 volume
> 4.0 KPI 0.5508680555555555
> 4.0
OsId 12 Cluster 9 BrowserId 16 PageId 1018637 conversion 4.0 volume 12.0 KPI 0.321111111111111
> 16.0
OsId 11 Cluster 9 BrowserId 17 PageId 1154705 conversion 13.0 volume 33.0 KPI 0.3886526452221044
> 49.0
OsId 99 Cluster 9 BrowserId 12 PageId 955761 conversion 11.0 volume 33.0 KPI 0.3366657218442933
> 82.0
OsId 12 Cluster 9 BrowserId 12 PageId 955767 conversion 7.0 volume 29.0 KPI 0.2346455795175744
> 111.0 Packed Knapsack Volume Value: 111.0 impression number 5 Packed Knapsack KPI: 0.3663886226501277
>
> Bag 3
>
> OsId 99 Cluster 4 BrowserId 16 PageId 1109643 conversion 1.0 volume
> 4.0 KPI 0.3055555555555556
> 4.0
OsId 11 Cluster 4 BrowserId 11 PageId 1149586 conversion 6.0 volume 8.0 KPI 0.7676237922705315
> 12.0
OsId 11 Cluster 4 BrowserId 15 PageId 1149586 conversion 8.0 volume 33.0 KPI 0.2383133975812547
> 45.0
OsId 12 Cluster 4 BrowserId 16 PageId 1154705 conversion 10.0 volume 41.0 KPI 0.2528392857142857
> 86.0
OsId 12 Cluster 4 BrowserId 14 PageId 955767 conversion 4.0 volume 20.0 KPI 0.2225
> 106.0
Packed Knapsack Volume Value: 106.0 impression number 5 Packed Knapsack KPI: 0.35736640622432553
>
> Bag 4
>
> OsId 11 Cluster 15 BrowserId 17 PageId 1109643 conversion 5.0 volume
> 12.0 KPI 0.3877777777777778
> 12.0
OsId 11 Cluster 15 BrowserId 17 PageId 1187774 conversion 3.0 volume 12.0 KPI 0.236237684729064
> 24.0
OsId 11 Cluster 15 BrowserId 11 PageId 955765 conversion 10.0 volume 41.0 KPI 0.2319838228361533
> 65.0
OsId 11 Cluster 18 BrowserId 17 PageId 1074581 conversion 5.0 volume 16.0 KPI 0.300344742063492
> 81.0
OsId 11 Cluster 18 BrowserId 16 PageId 1148073 conversion 3.0 volume 4.0 KPI 0.6833333333333333
> 85.0 Packed Knapsack Volume Value: 85.0 impression number 5 Packed Knapsack KPI: 0.36793547214796407
>
> Bag 5
>
> OsId 11 Cluster 21 BrowserId 12 PageId 1016529 conversion 3.0 volume
> 8.0 KPI 0.3541076152683295
> 8.0
OsId 11 Cluster 21 BrowserId 12 PageId 1068379 conversion 3.0 volume 4.0 KPI 0.6711734693877551
> 12.0
OsId 12 Cluster 21 BrowserId 16 PageId 911433 conversion 5.0 volume 16.0 KPI 0.3160714285714284
> 28.0
OsId 11 Cluster 21 BrowserId 12 PageId 941080 conversion 2.0 volume 8.0 KPI 0.2876372053872053
> 36.0
OsId 12 Cluster 21 BrowserId 14 PageId 941080 conversion 2.0 volume 8.0 KPI 0.275
> 44.0
问题是我在同一个包或垃圾箱中发现了多个簇的物品，例如在包 1 中，我们发现了簇为 0 和 7 的物品。
我该如何解决这个问题？
您的“class 物品的约束被放置在 1 个背包中”
for i in data2['class']:
solver.Add(sum(x2[i,j] for j in data2['bags'])<=1)
确保每个 class 都放入某个背包中。不保证每个背包只能装一个class.
我想你必须添加
# Only one class per knapsack Constraint
for j in data1['bags']:
solver.Add(sum(x2[(i,j)]
for i in data2['class']) <= 1)
相反。