Implement Bin Packing problem with additional elastic constraints using pulp optimizer

Question

I am using python as a programming language and implementing a constraint of grouping similar lengths together satisfying the linear programming. Refer to the code shown below

import pulp
from itertools import product
import pandas as pd
import numpy as np

# DataFrame of item, weight, and length
df_updated = pd.DataFrame([['item1', 10, 'A'], ['item2', 20, 'B'],  ['item3', 20, 'C'], 
        ['item4', 20, 'B'], ['item5',10, 'A'], ['item6',10, 'B']], 
        columns = ['itemname', 'QuantityToGroup', 'Length'])

# Max weightage per bin
max_weight = 40

# Max bin to use
min_bins = int(np.ceil(round((df_updated['QuantityToGroup'].sum() / max_weight))))
max_bins = 3

problem = pulp.LpProblem("Grouping_lengths", pulp.LpMinimize)

# Variable to check, if we are using the bin or not
bin_used = pulp.LpVariable.dicts('is_bin_used', range(max_bins), lowBound=0, upBound=1, cat='Binary')

# Possible combinations to put the item in the bin
possible_item_in_bin = [(item_index, bin_num) for item_index, bin_num in product(df_updated.index, range(max_bins))]
item_in_bin = pulp.LpVariable.dicts('is_item_in_bin', possible_item_in_bin, lowBound=0, upBound=1, cat = 'Binary')

# Only one item in each bin
for item_index in df_updated.index:
    problem += pulp.lpSum([item_in_bin[item_index, bin_index] for bin_index in range(max_bins)]) == 1, f"Ensure that item {item_index} is only in one bin"

# Sum of quantity grouped in each bin must be less than max weight
for bin_index in range(max_bins):
    problem += pulp.lpSum(
            [item_in_bin[item_index, bin_index] * df_updated.loc[item_index, 'QuantityToGroup'] for item_index in df_updated.index]
        ) <= max_weight * bin_used[bin_index], f"Sum of items in bin {bin_index} should not exceed max weight {max_weight}"

# Length Constraints
lengths = list(df_updated.Length.unique())
for length in lengths:
    items_n = df_updated.index[df_updated['Length'] == length].tolist()
    if len(items_n) > 1:
        for bin in range(max_bins - 1):
            first_index = items_n[0]
            for item in items_n[1:]:
                constr = pulp.LpConstraint(item_in_bin[first_index, bin] - item_in_bin[item, bin], sense = 0, rhs = 0, name = f"place item {item} in bin {bin} if length number {length} is chosen for this bin")
                problem += constr

# Objective function to minimize bins used
problem += pulp.lpSum(bin_used[bin_index] for bin_index in range(max_bins)), "Objective: Minimize Bins Used"

problem.solve(pulp.PULP_CBC_CMD(msg = False))


for val in problem.variables():
    if val.varValue == 1:
       print(val.name, val.varValue)

For the given input code is unable to group items of length B as the total weight for length B is (item 2 -> 20, item 4 -> 20, and item 6 -> 10) 50 which is greater than max weight 40. The code is working as expected.

But I have to make the length constraint elastic, which means it is okay to violate the constraint but the penalty should be added if the constraint is violated. I have explored Elastic Constraints which I think are exactly for my kind of requirement.

But I am facing an issue to implement them holding the linearity of the problem. Do I have to formulate my constraint in a different manner? Any help is appreciated.

Possible expected Output from the code making sure the objective of minimizing the wastage is respected and constraint is followed. If the constraint is not followed then the penalty is added.

# item 1 (A - 10), item 5 (A - 10), item3 (C - 20) on 1st bin. 
# item 2 (B) and item 4 (B) on 2nd bin.
# item 6 (B - 10) on 3rd bin

I have also tried alternative ways to formulate the length constraint section as shown below:

# Length Variable
lengths = list(df_updated.length.unique())

# Possible combinations to put the lengths in the bin
possible_length_in_bin = [(length, bin_num) for length, bin_num in product(range(len(lengths)), range(max_bins))]

# Constraint to group similar lengths together on same bin
length_in_bin = pulp.LpVariable.dicts('LengthInBin', possible_length_in_bin, cat = 'Binary')
for item, length, bins_index in product(df_updated.index, range(len(lengths)), range(max_bins)):
    problem += pulp.lpSum(item_in_bin[(item, bins_index)] == length_in_bin[(length, bins_index)]), (f"Only place item {item} in bin {bins_index} if length number {length} is chosen for this bin")

The rest of the section remains the same as above. But still, the solution doesn't return desired results.

Answer 1

Here is a solution that I think answers the mail. It is still linear. You need to introduce a couple of variables to count things such as the number of different lengths in a particular bin.

Some of those variables require a "big M" type constraint to link a binary variable to a summation.

Then with that variable in hand, you can add a small (or large?) penalty for "overloading" a bin with more than one length type.

Looking at this again, the tot_bins variable could be removed and just replaced by the lpSum(bin_used[b] for b in bins) anywhere, but it is clear as written.

I reformatted the code with black, which I'm not sure I'm fond of yet, but at least it is consistent. :)

Code

import pulp
from itertools import product
import pandas as pd
import numpy as np

# DataFrame of item, weight, and length
df_updated = pd.DataFrame(
    [
        ["item1", 10, "A"],
        ["item2", 20, "B"],
        ["item3", 20, "C"],
        ["item4", 20, "B"],
        ["item5", 10, "A"],
        ["item6", 10, "B"],
    ],
    columns=["itemname", "QuantityToGroup", "Length"],
)
lengths = list(df_updated.Length.unique())

# Max weightage per bin
max_weight = 40

# big M for number of items
big_M = len(df_updated)

# Max bin to use
min_bins = int(np.ceil(round((df_updated["QuantityToGroup"].sum() / max_weight))))
max_bins = 3
bins = list(range(max_bins))

problem = pulp.LpProblem("Grouping_lengths", pulp.LpMinimize)

# Variable to check, if we are using the bin or not
bin_used = pulp.LpVariable.dicts(
    "is_bin_used", bins, cat="Binary"
)

# Indicator that items of dimension d are located in bin b:
loaded = pulp.LpVariable.dicts(
    "loaded", [(d, b) for d in lengths for b in bins], cat="Binary"
)

# the total count of bins used
tot_bins = pulp.LpVariable("bins_used")

# the total count of overloads in a bin.  overload = (count of dimensions in bin) - 1
overload = pulp.LpVariable.dicts("bin_overloads", bins, lowBound=0)

# Possible combinations to put the item in the bin
possible_item_in_bin = [
    (item_index, bin_num) for item_index, bin_num in product(df_updated.index, bins)
]
item_in_bin = pulp.LpVariable.dicts(
    "is_item_in_bin", possible_item_in_bin, cat="Binary"
)

# Force each item to be loaded...
for item_index in df_updated.index:
    problem += (
        pulp.lpSum([item_in_bin[item_index, bin_index] for bin_index in bins]) == 1,
        f"Ensure that item {item_index} is only in one bin",
    )

# Sum of quantity grouped in each bin must be less than max weight
for bin_index in bins:
    problem += (
        pulp.lpSum(
            [
                item_in_bin[item_index, bin_index]
                * df_updated.loc[item_index, "QuantityToGroup"]
                for item_index in df_updated.index
            ]
        )
        <= max_weight * bin_used[bin_index],
        f"Sum of items in bin {bin_index} should not exceed max weight {max_weight}",
    )

# count the number of dimensions (lengths) in each bin
for b in bins:
    for d in lengths:
        problem += loaded[d, b] * big_M >= pulp.lpSum(
            item_in_bin[idx, b] for idx in df_updated.index[df_updated.Length == d]
        )

# attach the "bin used" variable to either the "loaded" var or "item in bin" var...
for b in bins:
    problem += bin_used[b] * big_M >= pulp.lpSum(
        item_in_bin[idx, b] for idx in df_updated.index
    )

# count total bins used
problem += tot_bins >= pulp.lpSum(bin_used[b] for b in bins)

# count the overloads by bin
for b in bins:
    problem += overload[b] >= pulp.lpSum(loaded[d, b] for d in lengths) - 1


# Objective function to minimize bins used, with some small penalty for total overloads
usage_wt = 1.0
overload_wt = 0.2

problem += (
    usage_wt * tot_bins + overload_wt * pulp.lpSum(overload[b] for b in bins),
    "Objective: Minimize Bins Used, penalize overloads",
)

problem.solve(pulp.PULP_CBC_CMD(msg=False))
status = pulp.LpStatus[problem.status]
assert(status=='Optimal')  # <--- always ensure this before looking at result if you don't print solve status


print(f"total bins used: {tot_bins.varValue}")
print("bin overloads:")
for b in bins:
    if overload[b].varValue > 0:
        print(f"    bin {b} has {overload[b].varValue} overloads")

for idx, b in possible_item_in_bin:
    if item_in_bin[idx, b].varValue == 1:
        print(
            f"load {df_updated.itemname.iloc[idx]}/{df_updated.Length.iloc[idx]} in bin {b}"
        )

Result:

total bins used: 3.0
bin overloads:
    bin 0 has 1.0 overloads
load item1/A in bin 0
load item2/B in bin 2
load item3/C in bin 1
load item4/B in bin 2
load item5/A in bin 0
load item6/B in bin 0