I'm trying to use PyMathProg for solving Bin Packing Problem the scripts are as follows:
import numpy as np
# bin packing problem
# create set of items weight
Wght = [11, 73, 13, 37, 51, 17, 39, 29, 23, 19]
# creating index set of Wght
Wg = range(len(Wght))
# maximum bin(vehicle) capacity
Cbin = 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 = 
for i in range(len(Wght)):
for j in range(len(Bins)):
Xij = (i, j)
# create LP model named 'BinPk'
p = pymprog.model('BinPk')
# creating varibles Yj
Yvar = p.var(Bins, 'Y', bool)
# creating Xij
Xvar = p.var(X, 'X', bool)
# objective function : minimize number of vehicle(bin) used
p.min(sum(Yvar[j] for j in Bins), 'Nbin')
# bin capacity must not exceed
p.st([sum(Wght[i] * Xvar[i,k] for i in Wg if (i,k) in X) <= Cbin*Yvar[k] for k in Bins], '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 vehicle
p.st([sum(Xvar[k,j] for j in Bins if (k,j) in X) == 1 for k in Wg], 'demand once')
print "MIP done >>>", p.status()
NBin = (p.vobj())
print "Number of bin used = ", NBin
loads = [x for x in Xvar if Xvar[x].primal > 0.5]
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?
Log in to post a comment.
Sign up for the SourceForge newsletter:
You seem to have CSS turned off.
Please don't fill out this field.