使用可变的bin成本和大小进行bin打包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

您要描述的具有可变装箱尺寸的装箱问题的变体至少是np-hard。

我不知道软件包openopt，项目网站似乎已关闭。Openopt似乎使用GLPK作为混合整数程序来解决该问题。您没有直接访问模型公式的权限，因为BPP（）是抽象的。您可能需要修改openopt软件包以为各个容器添加约束。

通常，添加可变仓位大小作为约束很容易，如果需要扩展此公式，则需要将索引i添加到容量V，以便每个仓位具有不同的容量。

我建议查看一些维护的库来建模和解决此问题：有库PuLP，CyLP和SCIP。我认为，后者并非免费用于商业用途。

由于装箱是一个非常普遍的问题，所以我找到了PuLP库的示例。我认为它默认使用CoinOR解算器，您也可以使用其他商业解决方案。

easy_install pulp

在安装PuLP之后（可以使用easy_install实现该功能），可以扩展此示例。我根据您的问题修改了示例：

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（）等抽象层的限制。