1

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.

Improve this question
5
  • The variable you are inspecting is declared to be binary. How could it be expected to take the value 2.0? Commented Jul 25, 2022 at 15:35
  • @AirSquid I have updated variables. And I have also updated expected output. You are correct. Expected output should be binary. But the 2 and 3 item should be in second bin. Commented Jul 25, 2022 at 17:37
  • Can you always place all items of the same length in the same bin? (I would say, this could easily exceed the bin capacity -- although I am not sure there are capacities.) If affirmative, then just replace these items of the same length with a single super item during preprocessing. That will, guaranteed, be placed in a single bin. Anyway, I highly recommend focusing on a proper mathematical model before staring at code. Commented Jul 26, 2022 at 1:31
  • “Group” does not imply “sending to different bins”. “Group” means “steak together” and those items you put into the group are placed on the same bin. So the solution is 100% correct. Maybe you have a different kind of statement in mind: items of different lengths must go to different bins. That is not a linear constraint (if you have more than 2 bins). It can be linearized by introducing supplemental variables or treated with SAT solver. Commented Jul 26, 2022 at 11:43
  • @AskoldIlvento I have updated the code and changes are mentioned in edits. You are correct in saying that my length constraint is not linear. I am facing an issue to make it linear. Could you help with a code snippet that can help to make the constraint linear? Commented Jul 27, 2022 at 7:27

1 Answer 1

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.