current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 1 down vote favorite

I am trying to solve the Bin Packing Problem using the Integer Programming Formulation in Python PuLP. The model for the problem is as follows:

enter image description here

I have written the following Python Code using the PuLP library

from pulp import *

#knapsack problem

def knapsolve(bins, binweight, items, weight):

    prob = LpProblem('BinPacking', LpMinimize)

    y = [LpVariable("y{0}".format(i+1), cat="Binary") for i in range(bins)]

    xs = [LpVariable("x{0}{1}".format(i+1, j+1), cat="Binary")
          for i in range(items) for j in range(bins)]

    #minimize objective
    nbins = sum(y)
    prob += nbins

    print(nbins)

    #constraints

    prob += nbins >= 1

    for i in range(items):
        con1 = sum(xs[(i * bins) + j] for j in range(bins))
        prob += con1 == 1
        print(con1)

    for k in range(bins):
        x = xs[k*bins : (k+1)*bins]
        con1 = sum([x1*y for x1, y in zip(x, weight)])
        prob += con1 <= binweight[k]
        print(con1)

    exec('prob')

    status = prob.solve()

    print(LpStatus[status])
    print("Objective value:", value(prob.objective))
    print ('\nThe values of the variables : \n')

    for v in prob.variables():
        print(v.name, "=", v.varValue)

    return

def knapsack():

    #bins

    bins = int(input ('Enter the upper bound on the number of bins:'))

    print ('\nEnter {0} bins\' capacities one by one'.format(bins))

    binweight = []

    for i in range(0, bins):
        print('Enter {0} bin capacity'.format(i+1))
        binweight.append(int(input()))

    for i in range(0, bins):
        print('The capacity at {0} is {1}'.format(i, binweight[i]))

    #items

    items = int(input('Enter the number of items:'))

    weight = []

    print ('\nEnter {0} items weights one by one'.format(items))

    for i in range(0, items):
        print('Enter {0} item weight'.format(i+1))
        weight.append(int(input()))

    for i in range(0, items):
        print('The weight at {0} is {1}'.format(i, weight[i]))

    knapsolve(bins, binweight, items, weight)

    return

knapsack()

Here is a sample run of the code :

Enter the upper bound on the number of bins:3

Enter 3 bins' capacities one by one
Enter 1 bin capacity
6
Enter 2 bin capacity
4
Enter 3 bin capacity
5
The capacity at 0 is 6
The capacity at 1 is 4
The capacity at 2 is 5
Enter the number of items:3

Enter 3 items weights one by one
Enter 1 item weight
5
Enter 2 item weight
1
Enter 3 item weight
2
The weight at 0 is 5
The weight at 1 is 1
The weight at 2 is 2
y1 + y2 + y3
x11 + x12 + x13
x21 + x22 + x23
x31 + x32 + x33
5*x11 + x12 + 2*x13
5*x21 + x22 + 2*x23
5*x31 + x32 + 2*x33
Optimal
Objective value: 1.0

The values of the variables : 

x11 = 0.0
x12 = 1.0
x13 = 0.0
x21 = 0.0
x22 = 0.0
x23 = 1.0
x31 = 0.0
x32 = 1.0
x33 = 0.0
y1 = 0.0
y2 = 0.0
y3 = 1.0

The output is not as expected. How do I specify the above constraints properly to get the correct output?

share|improve this question
up vote 1 down vote accepted

You can check the resulting LP/MIP model by writing it to a file after you build the problem:

...
prob.writeLP("binpacking")
status = prob.solve()
...

Now if you take a look at the binpacking file:

\* BinPacking *\
Minimize
OBJ: y1 + y2 + y3
Subject To
_C1: y1 + y2 + y3 >= 1
_C2: x11 + x12 + x13 = 1
_C3: x21 + x22 + x23 = 1
_C4: x31 + x32 + x33 = 1
_C5: 5 x11 + x12 + 2 x13 <= 6
_C6: 5 x21 + x22 + 2 x23 <= 4
_C7: 5 x31 + x32 + 2 x33 <= 5
Binaries
x11
x12
x13
x21
x22
x23
x31
x32
x33
y1
y2
y3
End

The constraints for bin capacities are not right. They are working as if all the bins are used without assigning 1's to the variables. It's because you are overwriting y value while using item weights.

You need to change those constraints like this:

for k in range(bins):
    x = xs[k*bins : (k+1)*bins]
    con1 = sum([x1*w for x1, w in zip(x, weight)])
    prob += con1 <= binweight[k] * y[k]
    print(con1)

Now they will be modeled as follows:

_C5: 5 x11 + x12 + 2 x13 - 6 y1 <= 0
_C6: 5 x21 + x22 + 2 x23 - 4 y2 <= 0
_C7: 5 x31 + x32 + 2 x33 - 5 y3 <= 0

Also, the indices for items constraints are not correct. Instead of x11 + x12 + x13 = 1 it should be x11 + x21 + x31 = 1

You can correct it like this:

for i in range(items):
    con1 = sum(xs[(i + j*bins)] for j in range(bins))
    prob += con1 == 1
    print(con1)

The constraints will be:

_C2: x11 + x21 + x31 = 1
_C3: x12 + x22 + x32 = 1
_C4: x13 + x23 + x33 = 1
share|improve this answer
    
Can you explain a bit more on the indices for items constraint? It works fine now, but what was I doing wrong? – Kaustabha Ray Mar 27 at 10:44
1  
From the definition of xij, xij=1 if item j is put into bin i. If you model it like x11 + x12 + x13 = 1, it means put at least one of the items in bin 1 (same for bin 2 and bin 3 - meaning all bins should be used). But what you want is put item j into at least one of the bins. That's why you need x11 + x21 + x31 = 1 It means put the first item into bin 1, bin 2 or bin 3. – ayhan Mar 27 at 10:48
    
What about the multiplication with y[k]? It's not present in the model, so why does that come into play? – Kaustabha Ray Mar 27 at 10:53
    
The variable yi is used to check if bin i is used. Now if you don't multiply the capacity with yi, the capacity will be usable even if you assign yi=0. It is actually presented in the model by V*yi on the right hand side of the first constraint set. – ayhan Mar 27 at 10:57
    
Oh yes I understand now – Kaustabha Ray Mar 27 at 11:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.