使用可变的bin成本和大小进行bin打包Python查询 [英] Bin packing Python query with variable bin cost and sizes

问题描述

我目前正在处理一个需要解决垃圾箱包装问题的问题。我的问题不同，因为垃圾箱的数量是有限的。我有三个垃圾箱，最小的一个垃圾箱放入物体的成本最低，中型垃圾箱比小垃圾箱稍贵，第三个垃圾箱理论上没有限制的容量，但是放入物品的成本高得多。

I'm currently working on a problem that requires a variation of the bin packing problem. My problem is different in that the number of bins is finite. I have three bins, the smallest one costs the least to put an object into, the medium bin is slightly more expensive than the small box, and the third box has theoretically unlimited capacity but is prohibitively more expensive to place an item into.

我能够在线找到一个Python脚本，以类似的方式解决了bin问题。我的问题是如何重写脚本以更接近最初的问题？有问题的脚本使用相同的垃圾箱。

I was able to find a Python script online that solves the bin problem in a similar manner. My question is how can I rewrite the script to get closer to my original problem? The script in question uses identical bins.

我在最底部添加了几行内容，讨论我希望垃圾箱看起来如何。此外，是否有办法为每个bin设置单独的约束？谢谢所有帮助！

I've included some lines at the very bottom to discuss how I would prefer the bin to look. Furthermore, is there a way to set up separate constraints for each bin? Thanks for all the help!

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,
    }

推荐答案

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

The variant of the bin packing problem with variable bin sizes you are describing is at least np-hard.

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

I do not know the package openopt, the project website seems to be down. Openopt seems to use GLPK to solve the problem as a mixed-integer program. You do not have direct access to the model formulation, since BPP() is an abstraction. You may need to modify the openopt package to add constraints for the individual bins.

通常，很容易将可变容器大小添加为约束，从而扩展了此公式，您需要将索引i添加到容量V中，以便每个容器具有不同的容量。

It is generally easy to add the variable bin sizes as a constraint, extending this formulation you would need to add index i to capacity V, so that each bin has a different capacity.

我建议查看一些维护的库以建模并解决此问题：有库 PuLP ， CyLP 和 SCIP 。

I would recommend to look at some maintained libraries to model and solve this problem: There is the library PuLP, CyLP and SCIP. The latter is not free for commercial use I think though.

由于bin打包是一个非常普遍的问题，因此我找到了PuLP库的示例。我认为默认情况下，它使用CoinOR解算器。您也可以使用其他商业解决方案。

Since bin packing is a very common problem, I found an example for the PuLP library. It uses the CoinOR Solver by default I think, you can also use different commercial ones.

easy_install pulp

在安装PuLP之后，easy_install应该可以实现，您可以在此示例。
我根据您的问题修改了示例：

After installing PuLP, which should be possible with easy_install you can extend on this example. I modified the example according to your problem:

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

This implementation has the strong advantage that you have complete control over your model formulation and you are not restricted by some layer of abstraction like BPP() in the case of openopt.

这篇关于使用可变的bin成本和大小进行bin打包Python查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！