Dear all,

I'm trying to use PyMathProg for solving Bin Packing Problem the scripts are as follows:

import numpy as np import pymprog # 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) X.append(Xij) # 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') # constraints # 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') p.solve(float) p.solve(int) 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] print loads

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?