二维装箱

Question

我正在使用以下整数规划模型来解决二维装箱问题。以下模型说明了一维版本。我编写的代码包含了附加维度的约束。

我正在使用 Python PuLP 来解决优化问题。代码如下：

from pulp import *

#knapsack problem

def knapsolve(item):

    prob = LpProblem('BinPacking', LpMinimize)

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

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

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

    print(nbins)

    #constraints

    t = nbins >= 1
    print(t)
    prob += t

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

    for k in range(item.bins):
        x = xs[k*item.bins : (k+1)*item.bins]
        con1 = sum([x1*w for x1, w in zip(x, item.itemweight)])
        t = con1 <= item.binweight[k] * ys[k]
        #t = con1 <= item.binweight[k]
        prob += t
        print(t)

    for k in range(item.bins):
        x = xs[k*item.bins : (k+1)*item.bins]
        con1 = sum([x1*w for x1, w in zip(x, item.itemheight)])
        t = con1 <= item.binheight[k] * ys[k]
        #t = con1 <= item.binheight[k]
        prob += t
        print(t)

    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

class Item:
    #bins, binweight, items, weight, itemheight, binheight

    bins = 5
    items = 5

    binweight = [2,3,2,5,3]
    itemweight = [1,2,2,1,3]

    itemheight = [2,1,4,5,3]
    binheight = [4,9,10,8,10]


item = Item()

knapsolve(item)

它产生以下输出：

y1 + y2 + y3 + y4 + y5
y1 + y2 + y3 + y4 + y5 >= 1
x11 + x21 + x31 + x41 + x51 = 1
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 1
x14 + x24 + x34 + x44 + x54 = 1
x15 + x25 + x35 + x45 + x55 = 1
x11 + 2*x12 + 2*x13 + x14 + 3*x15 - 2*y1 <= 0
x21 + 2*x22 + 2*x23 + x24 + 3*x25 - 3*y2 <= 0
x31 + 2*x32 + 2*x33 + x34 + 3*x35 - 2*y3 <= 0
x41 + 2*x42 + 2*x43 + x44 + 3*x45 - 5*y4 <= 0
x51 + 2*x52 + 2*x53 + x54 + 3*x55 - 3*y5 <= 0
2*x11 + x12 + 4*x13 + 5*x14 + 3*x15 - 4*y1 <= 0
2*x21 + x22 + 4*x23 + 5*x24 + 3*x25 - 9*y2 <= 0
2*x31 + x32 + 4*x33 + 5*x34 + 3*x35 - 10*y3 <= 0
2*x41 + x42 + 4*x43 + 5*x44 + 3*x45 - 8*y4 <= 0
2*x51 + x52 + 4*x53 + 5*x54 + 3*x55 - 10*y5 <= 0
Optimal
Objective value: 3.0

The values of the variables : 

x11 = 0.0
x12 = 0.0
x13 = 0.0
x14 = 0.0
x15 = 0.0
x21 = 0.0
x22 = 0.0
x23 = 1.0
x24 = 0.0
x25 = 0.0
x31 = 0.0
x32 = 0.0
x33 = 0.0
x34 = 0.0
x35 = 0.0
x41 = 0.0
x42 = 1.0
x43 = 0.0
x44 = 0.0
x45 = 1.0
x51 = 1.0
x52 = 0.0
x53 = 0.0
x54 = 1.0
x55 = 0.0
y1 = 0.0
y2 = 1.0
y3 = 0.0
y4 = 1.0
y5 = 1.0

经过硬编码的示例输入数据应产生 1 个 bin 作为输出，即一个 y 变量的值应为 1。但事实并非如此。方程式是否正确建模？还有另一种指定约束的方法吗？

Answer 1

标准装箱问题的数学模型使用 x(bins,items)，而在 Python 模型中，您似乎混合使用了 x(bins,items) 和 x(items,bins)。对 xs 的赋值使用 x(items,bins)，但构造 xs[(i + j*item.bins)] 暗示 x(bins,items)。通过检查输出很容易看出这一点：x11 + x21 + x31 + x41 + x51 = 1 表示 x(bins,items)。这种具有显式指数计算的建模在实践中是相当不可靠的。这是一个玩具模型，但对于真正的模型来说，缺少类型检查是非常危险的。

不同的垃圾箱重量和高度应该没问题。

也给出了你的数据

binweight = [2,3,2,5,3]
itemweight = [1,2,2,1,3]   
itemheight = [2,1,4,5,3]
binheight = [4,9,10,8,10]

我不相信这可以像您所说的那样仅用 1 个垃圾箱就可以处理。为此，您需要 3 个箱子（箱子 2,4 和 5）。（你在这里很幸运，因为尽管 Python 代码中实际上存在错误，但你得到了很好的解决方案）。

二维装箱

Two Dimensional Bin Packing

python

mathematical-optimization

linear-programming

integer-programming

pulp