2

2 次元ビン パッキング問題を解決するために、次の整数計画モデルを使用しています。次のモデルは、1 次元バージョンを示しています。私が書いたコードには、追加の次元の制約が組み込まれています。

ここに画像の説明を入力

最適化問題を解決するために 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 つのビンを生成する必要があります。つまり、1 つの y 変数の値は 1 になります。ただし、そうではありません。方程式は適切にモデル化されていますか? 制約を指定する別の方法はありますか?

4

1 に答える 1

1

標準のビンパッキング問題の数学的モデルでは、Python モデルではと をx(bins,items)組み合わせて使用​​しているように見えますが、 を使用しています。への代入は使用しますが、構造は を意味します。これは、出力を調べることで簡単に確認できます。明示的な指数計算を伴うこのタイプのモデリングは、実際にはかなり信頼できません。これはおもちゃのモデルですが、実際のモデルの場合、型チェックの欠如は非常に危険です。x(bins,items)x(items,bins)xsx(items,bins)xs[(i + j*item.bins)]x(bins,items)x11 + x21 + x31 + x41 + x51 = 1x(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 コードには実際にはバグがありますが、良い解決策が得られるので、ここでは幸運です)。

于 2016-04-09T20:08:41.673 に答える