1

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

在此处输入图像描述

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

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()

这是代码的示例运行：

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

输出不如预期。如何正确指定上述约束以获得正确的输出？

4

1 回答 1

2

您可以在构建问题后通过将其写入文件来检查生成的 LP/MIP 模型：

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

现在，如果您看一下 binpacking 文件：

\* 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在使用项目权重时覆盖了值。

您需要像这样更改这些约束：

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)

现在它们将被建模如下：

_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

您可以像这样更正它：

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
于 2016-03-27T10:07:29.993 回答