I'm trying to use PyMathProg for solving Bin Packing Problem the scripts are as follows:
importnumpyasnpimportpymprog# bin packing problem# create set of items weight Wght=[11,73,13,37,51,17,39,29,23,19]# creating index set of WghtWg=range(len(Wght))# maximum bin(vehicle) capacityCbin=80.0# minimum number of bins required Nbin=int(np.ceil(sum(Wght)/Cbin))# create list of bins #Bins = range(len(Wght))Bins=range(Nbin+1)#creating index set expressing "item i goes to bin j"X=[]foriinrange(len(Wght)):forjinrange(len(Bins)):Xij=(i,j)X.append(Xij)# create LP model named 'BinPk' p=pymprog.model('BinPk')# creating varibles Yj Yvar=p.var(Bins,'Y',bool)# creating XijXvar=p.var(X,'X',bool)# objective function : minimize number of vehicle(bin) usedp.min(sum(Yvar[j]forjinBins),'Nbin')# constraints# bin capacity must not exceedp.st([sum(Wght[i]*Xvar[i,k]foriinWgif(i,k)inX)<=Cbin*Yvar[k]forkinBins],'capacity')#p.st([sum(Wght[i] * Xvar[i,k] for i in Wg if (i,k) in X) <= Cbin for k in Bins], 'capacity')# each demand is taken care once by only one vehiclep.st([sum(Xvar[k,j]forjinBinsif(k,j)inX)==1forkinWg],'demand once')p.solve(float)p.solve(int)print"MIP done >>>",p.status()NBin=(p.vobj())print"Number of bin used = ",NBinloads=[xforxinXvarifXvar[x].primal>0.5]printloads
according to the lecture I've taken, this should results as NBin = 4 with the following packing assignment:
after I run it, the results is 4 bin but the packing assignment are all wrong (almost every items are in one bin). I checked the bin capacity constraints and it seems to correct. Am I missing something here?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Dear all,
I'm trying to use PyMathProg for solving Bin Packing Problem the scripts are as follows:
according to the lecture I've taken, this should results as NBin = 4 with the following packing assignment:
bin#1 => 11, 13, 37, 39
bin#2 => 73
bin#3 => 51, 29
bin#4 => 17, 39, 23
after I run it, the results is 4 bin but the packing assignment are all wrong (almost every items are in one bin). I checked the bin capacity constraints and it seems to correct. Am I missing something here?