How to apply a binary constraint on a binary variable in pulp?

Question

I am using python as a programming language and trying to implement a binary constraint on a binary variable. But the constraint is not getting applied and the results are not 100% correct.

In the below code snippet I want to place the items with the same length in one bin. (This is only a subproblem of the bigger picture and I need to solve it using pulp only).

import pulp
from itertools import product
import pandas as pd

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

# Max bin to use
max_bins = 2

# Max weightage per bin
max_weight = 30

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), 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, 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, 'weight'] 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 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")

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

Results from the algorithm: (All items are placed in same bin)

is_item_in_bin_(0,_0) 1.0
is_item_in_bin_(1,_1) 1.0
is_item_in_bin_(2,_1) 1.0
is_item_in_bin_(3,_0) 1.0

Expected Result from the algorithm: (Similar length items should only be grouped together)

is_item_in_bin_(0,_0) 1.0
is_item_in_bin_(1,_0) 1.0
is_item_in_bin_(2,_1) 1.0
is_item_in_bin_(3,_1) 1.0

As I have a length constraint to group similar lengths on the bin. Could you help and let me know what I am doing wrong here?

EDIT: I have updated the code to include max size per bin. Now I have a max capacity of 30 per bin and at max, I want to use 2 bins only. I have also added the constraint to add same-length items to the bin. But the constraint is violated again and items of different lengths are added to the same bin even though the objective value would have been the same.

Answer 1

As I’ve written in the comments the anti-affinity constraint (spread to different bins) is non-linear, but usually can be linearized. In contrast, affinity constraint (to the same bin) is linear and simple. It is just equality of assignment variables.
As Erwin Kalvelagen has suggested, it would be better to eliminate such constraints and reduce the number of variables. But anyway if they are needed then:

same part

import pulp
from itertools import product
import pandas as pd

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

# Max bin to use
max_bins = 2

# Max weightage per bin
max_weight = 30

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), 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, 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, 'weight'] 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}"

different part

 # Length Constraints
lengths = list(df_updated.length.unique())
for length in lengths:
    items_n = df_updated.index[df_updated['length'] == length].tolist()  # get items with given length
    if len(items_n) > 1:  # skip items with unique length
        for bin in range(max_bins - 1):  # for each bin except the last one because the last can be deduced
            for item in range(1, len(items_n)):  # set other item assignment equal to the first one.
                problem += item_in_bin[0, bin] == item_in_bin[item, bin]

same part

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

The results from the algorithm:

is_bin_used_0 1.0
is_bin_used_1 1.0
is_item_in_bin_(0,_1) 1.0
is_item_in_bin_(1,_1) 1.0
is_item_in_bin_(2,_0) 1.0
is_item_in_bin_(3,_0) 1.0

Same length items are grouped together. Others are put in a different bin due to the max_weight constraint.