OR-Tools bin packing: Ensuring items with the same supplier are in the same bin while considering capacity constraints

Question

I am working on a bin packing problem using OR-Tools and the SCIP solver. I have followed the guide provided by Google on bin packing (Google OR-Tools Bin Packing Guide).

I have successfully implemented the algorithm and achieved the objective of minimizing the number of bins used. Additionally, I have incorporated capacity constraints to ensure that the amount packed in each bin does not exceed its capacity (based on CBM and weight).

However, I'm facing difficulties in modifying the algorithm to further minimize the number of suppliers in bins. My goal is to ensure that items from the same supplier are placed in the same bin whenever possible. However, if all the items from the same supplier exceed the bin's capacity (CBM or weight), I am willing to split them across multiple bins.

I have tried several approaches but haven't been able to find a suitable solution. I would appreciate any guidance or suggestions on how to modify the code to achieve this requirement. Specifically, I need help in adapting the constraints and the objective function.

Here is an excerpt of the relevant code:

    def __variables__(self):
            # Variables
            # x[i, j] = 1 if item i is packed in bin j.
            x = {}
            for i in self.model['data']:
                for j in self.model['bins']:
                    x[(i, j)] = self.solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
    
            # y[j] = 1 if bin j is used.
            y = {}
            for j in self.model['bins']:
                y[j] = self.solver.IntVar(0, 1, 'y[%i]' % j)
    
            self.variables = [x, y]
    
        def __constraints__(self):
            if not self.variables or not self.solver:
                return
            x = self.variables[0]
            y = self.variables[1]
            # Constraints
            # Each item must be in exactly one bin.
            for i in self.model['data']:
                self.solver.Add(sum(x[i, j] for j in self.model['bins']) == 1)
    
            # The amount packed in each bin cannot exceed its capacity.
            for j in self.model['bins']:
                self.solver.Add(
                    sum(x[(i, j)] * self.model['cbms'][i] for i in self.model['data']) <= y[j] *
                    self.model['bin_capacity_cbm'])
                self.solver.Add(
                    sum(x[(i, j)] * self.model['weights'][i] for i in self.model['data']) <= y[j] *
                    self.model['bin_capacity_weight'])
    
            # Objective: minimize the number of bins used.
            self.solver.Minimize(self.solver.Sum(
                [y[j] for j in self.model['bins']]))
            # solver.Minimize(solver.Sum([ model['cbms'][j] for j in model['bins'] for i in model['suppliers'] if z[(j, i)] in model['bins'][i])])
    
        def create_model(self) -> Dict[str, List]:
            model = {'data': [], 'cbms': [], 'weights': [],
                     'items': [], 'suppliers': []}
            # Iterate through each item
            for item in self.items:
                model['weights'].append(item[WEIGHT])
                model['cbms'].append(item[CBM])
                model['items'].append(item)
                model['suppliers'].append(item[SUPPLIER])
    
            # Set the 'items' list as a range of indices based on the length of 'cbms'
            model['data'] = list(range(len(model['cbms'])))
            model['bins'] = model['data']
    
            model['bin_capacity_cbm'] = MAX_CBM
            model['bin_capacity_weight'] = MAX_WEIGHT
    
            self.model = model

Here is my input list of items:

    data = [
        {
            'asin': '...',
            'cbm': 0.728,
            'how_many_cartons': ...,
            'how_many_to_ship': '...',
            'optional': '',
            'port': 'Tianjin',
            'product_name': '...',
            'ready_date': '6/30/2023',
            'sku': '...',
            'supplier': 'HEBEI HOUDE HANFANG MEDICAL DEVICES GROUP CO.,LTD',
            'weight': 163.8
        },
        {
            'asin': '...',
            'cbm': 11.392,
            'how_many_cartons': ...,
            'how_many_to_ship': '...',
            'optional': '',
            'port': 'Shenzhen',
            'product_name': '...',
            'ready_date': 'Ready',
            'sku': '...',
            'supplier': 'HEBEI HOUDE HANFANG MEDICAL DEVICES GROUP CO.,LTD',
            'weight': 7048.8
        },
        {
            'asin': '...',
            'cbm': 5.6,
            'how_many_cartons': ...,
            'how_many_to_ship': '...',
            'optional': '',
            'port': 'Shenzhen',
            'product_name': '...',
            'ready_date': 'Ready',
            'sku': '...',
            'supplier': 'HongTaiDingYe',
            'weight': 1666.0
        },
        {
            'asin': '...',
            'cbm': 0.08,
            'how_many_cartons': ...,
            'how_many_to_ship': '...',
            'optional': '',
            'port': 'Shenzhen',
            'product_name': '...',
            'ready_date': '6/30/2023',
            'sku': '...',
            'supplier': 'HongTaiDingYe',
            'weight': 35.6
        }
    ]

Answer 1

So, for each supplier and each bin, you need a Boolean variable that will be True if the supplier is present in the bin.

So, we will use the standard encoding for this:

  supplier_present = model.NewBoolVar('supplier_present')
  items_from_supplier = [i1, .., ik]  # List of Boolean variables
  for item in in items_from_supplier:
    model.AddImplication(item, supplier_present)

  # Now the reverse implication.
  # If no item is present, then the supplier is not here.
  # We use an bool_or for this. If no item is present, the last element must be true
  model.AddBoolOr(items_from_supplier + [supplier_present.Not()])

Now you can use the newly created supplier_present variables in your objective, or in dedicated constraints.

Answer 2

To ensure that all items from the same supplier are placed in the same bin, you could introduce a new set of constraints using the z variable you have defined.

Here is how you might do this:

for k in self.model['suppliers']:
    for i in self.model['data']:
        if self.model['suppliers'][i] == k:  # if item i is supplied by supplier k
            for j in self.model['bins']:
                # Item i can only be in bin j if supplier k is assigned to bin j.
                self.solver.Add(x[i, j] <= z[k, j])

# Now ensure that each supplier is assigned to exactly one bin.
for k in self.model['suppliers']:
    self.solver.Add(sum(z[k, j] for j in self.model['bins']) == 1)

and update the create_model

 def __create_model__(self) -> Dict[str, List]:
        pprint(self.items)
        model = {'data': [], 'cbms': [], 'weights': [], 
                 'items': [], 'suppliers': []}

        supplier_ids = {}
        # Iterate through each item
        for item in self.items:
            model['weights'].append(item[WEIGHT])
            model['cbms'].append(item[CBM])
            model['items'].append(item)
            supplier = item[SUPPLIER]
            if supplier not in supplier_ids:
                supplier_id = len(supplier_ids)
                supplier_ids[supplier] = supplier_id
        # Set the 'items' list as a range of indices based on the length of 'cbms'
        model['data'] = list(range(len(model['cbms'])))
        model['bins'] = model['data']
        model['suppliers'] = [supplier_ids[item[SUPPLIER]] for item in self.items]
        model['bin_capacity_cbm'] = MAX_CBM
        model['bin_capacity_weight'] = MAX_WEIGHT

        self.model = model

The first loop and constraint ensure that an item i from a supplier k can only be in bin j if supplier k is assigned to bin j. The second loop and constraint ensure that each supplier is assigned to exactly one bin. This forces all items from the same supplier to go to the same bin because a supplier can only be associated with one bin.

Please note that this will work under the assumption that the bin has enough capacity to hold all items from a single supplier. If a single supplier provides more items than can fit into one bin, then this constraint will cause the problem to be infeasible. This also assumes that the number of bins is greater than or equal to the number of suppliers. In real scenarios, additional checks and balances might be needed to handle these edge cases.