Bin packing Python query with variable bin cost and sizes

Question

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.

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.

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

Tristan Tristan · Accepted Answer · 2017-02-25T01:42:24

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

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.

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.

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.

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

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

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 packing Python query with variable bin cost and sizes

1 Answers