How do I specify multiple variable constraints using Integer Programming in PuLP?

Question

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:

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?

e.g. multiple knapsack p.16

JeeyCi
– JeeyCi

2023-10-02 16:02:31 +00:00
Commented Oct 2, 2023 at 16:02 — JeeyCi
– JeeyCi, Commented Oct 2, 2023 at 16:02

score 2 · Accepted Answer · 2016-03-27 10:25:59Z

2

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

edited Mar 27, 2016 at 10:25

answered Mar 27, 2016 at 10:07

user2285236

Sign up to request clarification or add additional context in comments.

5 Comments

kauray Over a year ago

Can you explain a bit more on the indices for items constraint? It works fine now, but what was I doing wrong?

user2285236 Over a year ago

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.

kauray Over a year ago

What about the multiplication with y[k]? It's not present in the model, so why does that come into play?

user2285236 Over a year ago

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.

kauray Over a year ago

Oh yes I understand now

Collectives™ on Stack Overflow

How do I specify multiple variable constraints using Integer Programming in PuLP?

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related