如何在PuLP中使用整数编程来指定多个变量约束? [英] How do I specify multiple variable constraints using Integer Programming in PuLP?

问题描述

我正在尝试使用Python PuLP中的整数编程公式来解决装箱问题.该问题的模型如下:

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:

我已经使用PuLP库编写了以下Python代码

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?

推荐答案

在生成问题后，可以通过将生成的LP/MIP模型写入文件来检查生成的LP/MIP模型:

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

对箱容量的限制不正确.它们就像所有bin都在使用时一样工作，而没有为变量分配1.这是因为您在使用项目权重时会覆盖y值.

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

此外，项目约束的索引也不正确.而不是x11 + x12 + x13 = 1，它应该是x11 + x21 + x31 = 1

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

您可以像这样纠正它:

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

约束将是:

_C2: x11 + x21 + x31 = 1
_C3: x12 + x22 + x32 = 1
_C4: x13 + x23 + x33 = 1

这篇关于如何在PuLP中使用整数编程来指定多个变量约束?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！