2次元ビンパッキング

Question

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

---

私は、最適化問題を解決するためのPythonのパルプを使用しています。次のようにコードがある：

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つのビンを生成する必要があり、その一つの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)を示します。明示的なインデックス計算を伴うこのタイプのモデリングは、実際には信頼性があまりありません。これはおもちゃのモデルですが、実際のモデルでは型チェックの欠如は非常に危険です。

異なるビンの重みと高さは問題ありません。

はまた、私はあなたが主張するよう、これはちょうど1ビンで扱うことができると信じていないあなたのデータ

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

を与えられました。これには3つのビンが必要です（ビン2,4,5）。 （実際にはPythonコードにバグがありますが、良い解決策を得ることができますので、ここでは幸運です）。