Bin Packing with Variable Weight BPP - using PuLP

bpp_var_weight.py

from pulp import pulp, constants as pulp_constants

items = [("a", 2), ("b", 0.5), ("c", 0.5), ("d", 0.5), ("e", 0.5), ("f", 0.5)]

itemCount = len(items)
maxBins = 3
binCapacity = [4, 2, 2, 2] * 4
binCost = binCapacity

y = pulp.LpVariable.dicts('BinUsed',
                          range(maxBins),
                          lowBound=0,
                          upBound=1,
                          cat=pulp_constants.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_constants.LpInteger)

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

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

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

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

How do we extend this when maxBins is not known in advanced?

Consider this example where the solution is the number of bins required of a a particular bin type. Your solution considers different bin types but limits the max number of bins. How do "merge" both these solutions?