PyMathProg on Bin Packing Problem

[Jiravud Klongtrujrok]

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?