I am trying to solve a Multiple Knapsacks Problem in Python which consists on putting items in 5 bins and the constraint is that each bin(bag) must contains items with same cluster (so we must not find two object with different clusters in the same bin) and maximizing the sum KPI of items packed in the bins
Here is the dataframe data:
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
To solve it:
I created a first Assignment-matrix 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')
Variable 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))
Then, I add a second matrix : Assignment-matrix B item-classes <-> 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))
Then, I precise the list of constraints:
#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))
Then, I precise the optimization objective:
objective = solver.Objective()
for i in data1['items']:
for j in data1['bags']:
objective.SetCoefficient(x[(i,j)], data1['KPI'][i])
objective.SetMaximization()
Resolution
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")
And finally as result I get this five bins with their items:
> 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
The problem is I found in the same bag or bin item with multiple cluster for example in bag 1 we found items with cluster 0 and 7.
How can I fix this?
Your "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)
ensures that each class is placed into some knapsack. It does not ensure that each knapsack holds only one class.
I think you will have to add
# Only one class per knapsack Constraint
for j in data1['bags']:
solver.Add(sum(x2[(i,j)]
for i in data2['class']) <= 1)
instead.