bin可變bin成本和大小的bin包裝Python查詢

我目前正在研究一個需要bin包裝問題變化的問題。我的問題不同，因爲垃圾箱的數量是有限的。我有三個垃圾箱，其中最小的一個將物品放入的成本最低，中型垃圾箱比小型垃圾箱稍貴，第三個垃圾箱理論上具有無限容量，但放置物品的成本過高。bin可變bin成本和大小的bin包裝Python查詢

我能夠在網上找到一個Python腳本，以類似的方式解決了bin問題。我的問題是如何重寫腳本以接近我原來的問題？有問題的腳本使用相同的垃圾箱。

我已經在最下面列出了一些線條來討論如何選擇垃圾桶。此外，是否有辦法爲每個垃圾箱設置單獨的約束？感謝所有的幫助！

from openopt import * 

N = 30 #Length of loan dataset 

items = [] 
for i in range(N): 
    small_vm = { 
     'name': 'small%d' % i, 
     'cpu': 2, 
     'mem': 2048, 
     'disk': 20, 
     'n': 1 
     } 
    med_vm = { 
     'name': 'medium%d' % i, 
     'cpu': 4, 
     'mem': 4096, 
     'disk': 40, 
     'n': 1 
     } 
    large_vm = { 
     'name': 'large%d' % i, 
     'cpu': 8, 
     'mem': 8192, 
     'disk': 80, 
     'n': 1 
     } 
    items.append(small_vm) 
    items.append(med_vm) 
    items.append(large_vm) 



bins = { 
'cpu': 48*4, # 4.0 overcommit with cpu 
'mem': 240000, 
'disk': 2000, 
} 

p = BPP(items, bins, goal = 'min') 

r = p.solve('glpk', iprint = 0) 
print(r.xf) 
print(r.values) # per each bin 
print "total vms is " + str(len(items)) 
print "servers used is " + str(len(r.xf)) 

for i,s in enumerate(r.xf): 
    print "server " + str(i) + " has " + str(len(s)) + " vms" 




##OP Interjection: Ideally my bins would look something like: 
bin1 = { 
    'size': 10000, 
    'cost': 0.01*item_weight, 
    } 

bin2 = { 
    'size': 20000, 
    'cost': 0.02*item_weight, 
    } 

bin3 = { 
    'size': 100000, 
    'cost': 0.3*item_weight, 
    }

來源

2017-02-25 Don L

您所描述的變量箱尺寸的箱包裝問題的變體至少是np-hard。

我不知道包openopt，項目網站似乎是關閉了。 Openopt似乎使用GLPK來解決混合整數程序的問題。您無法直接訪問模型公式，因爲BPP（）是一個抽象。您可能需要修改openopt軟件包以爲各個倉添加約束。

通常容易將可變倉大小作爲約束條件添加，因此需要將索引i添加到容量V，以便每個倉具有不同的容量。

我建議看看一些維護庫來建模和解決這個問題：有庫PuLP,CyLP和SCIP。後者雖然不是免費的商業用途。

由於bin包裝是一個非常普遍的問題，我找到了一個PuLP庫的例子。它默認使用CoinOR求解程序，我認爲，您也可以使用不同的商業程序。

easy_install pulp

安裝紙漿，這應該是可能的，你的easy_install可以this example延長後。我根據您的問題修改的例子：

from pulp import * 

items = [("a", 5), ("b", 6), ("c", 7)] 

itemCount = len(items) 
maxBins = 3 
binCapacity = [11, 15, 10] 
binCost = [10, 30, 20] 

y = pulp.LpVariable.dicts('BinUsed', range(maxBins), lowBound = 0, upBound = 1, cat = pulp.LpInteger) 
possible_ItemInBin = [(itemTuple[0], binNum) for itemTuple in items for binNum in range(maxBins)] 
x = pulp.LpVariable.dicts('itemInBin', possible_ItemInBin, lowBound = 0, upBound = 1, cat = pulp.LpInteger) 

# Model formulation 
prob = LpProblem("Bin Packing Problem", LpMinimize) 

# Objective 
prob += lpSum([binCost[i] * y[i] for i in range(maxBins)]) 

# Constraints 
for j in items: 
    prob += lpSum([x[(j[0], i)] for i in range(maxBins)]) == 1 
for i in range(maxBins): 
    prob += lpSum([items[j][1] * x[(items[j][0], i)] for j in range(itemCount)]) <= binCapacity[i]*y[i] 
prob.solve() 

print("Bins used: " + str(sum(([y[i].value() for i in range(maxBins)])))) 
for i in x.keys(): 
    if x[i].value() == 1: 
     print("Item {} is packed in bin {}.".format(*i))

該實現，你可以完全控制你的模型公式具有強大的優勢，你是不是喜歡BPP（）的某種抽象層的情況下限制openopt。

來源

2017-02-25 01:42:24 Tristan

bin可變bin成本和大小的bin包裝Python查詢

回答

相關問題