python - 具有可变 bin 成本和大小的 bin packing Python 查询

Question

我目前正在处理一个需要变体装箱问题的问题。我的问题是不同的，因为箱子的数量是有限的。我有三个箱子，最小的箱子放东西成本最低，中号箱子比小箱子贵一点，第三个箱子理论上容量无限，但放东西贵得令人望而却步。

我能够在网上找到一个 Python 脚本，它以类似的方式解决了 bin 问题。我的问题是如何重写脚本以更接近我原来的问题？有问题的脚本使用相同的容器。

我在最底部添加了一些行来讨论我希望垃圾箱看起来如何。此外，有没有办法为每个 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,
    }

Answer 1

您描述的具有可变 bin 大小的 bin packing 问题的变体至少是 np-hard。

不知道openopt这个包，项目官网好像挂了。 Openopt 似乎使用 GLPK 作为混合整数程序来解决问题。您无法直接访问模型公式，因为 BPP() 是一种抽象。您可能需要修改 openopt 包以添加对各个 bin 的约束。

添加可变 bin 大小作为约束通常很容易，扩展 this formulation您需要将索引 i 添加到容量 V，以便每个箱子都有不同的容量。

我建议查看一些维护的库来建模和解决这个问题:有库 PuLP , CyLP和 SCIP .我认为后者不是免费用于商业用途。

由于装箱是一个非常普遍的问题，我找到了 PuLP 库的示例。我认为它默认使用 CoinOR 求解器，您也可以使用不同的商业求解器。

easy_install pulp

安装 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))

此实现具有强大的优势，您可以完全控制模型的制定，并且在 openopt 的情况下不受某些抽象层(如 BPP())的限制。