How do I specify multiple variable constraints usi

问题:

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?

回答1:

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