# Shipments consolidation - how to model mutually exclusive items with OR-Tools CP Solver in Python (multi-knapsack, updated)

I am implementing a solution for packages consolidation (basing on Nurse Problem solution) with OR-Tools CP Solver.

There is a factory that manufactures some small Packages that need to be transported by post to the customers. It would be optimal to consolidate some mini_Packages into bigger Packages (for example if we respect total weight limit, we can merge 3 light mini_Packages into one Package and pay transport costs once not 3 times).

Mini_Packages have some important attributes in data source (fixed destination, weight, acceptable delivery date range).

My main 0-1 integer variable looks like:

x[mini_package_number, optimal_shipment_date, package_number]


It == 1 if mini_Package should be send on a certain day, consolidated to a certain Package_number.

Conflicting products

A mini_Package represents a single product item. Name of the product is an attribute of mini_Package, given in a certain list (position on the list = mini_Package_number).

products = [34, 12, 12, 456 ...]
meaning that:
mini_Package 0 contains product 34
mini_Package 1 contains product 12
mini_Package 2 also contains product 12

There are some products that cannot be merged together. If a mini_Packages represent a certain product it cannot be merged (to the same Package) with another mini_Package that represents conflicting product.

The format of conflict matrix can be adjusted for the model.

At the moment I plan following format:

conflict_list = [(1,3), (3,6), (5,19)] saying that:
product 1 and 3 cannot go together
product 3 and 6 cannot go together
product 5 and 19 cannot go together

Conflict list represents mutually exclusive pairs, however it is important that final Package may merge more products (for example four mini_Packages with non-conflicting products 1, 1, 2, 6).

Do you have any ideas how such a logic could be implemented?

• Would a simple $x_1 + x_2 \le 1$ for each entry in conflict list do the trick? Oct 14, 2019 at 7:07

You can use the linear constraint function to add additional constraints which prohibit mutually exclusive pairs. I'd imagine that each mini package has to be scheduled on one date so this leads to the following code:

for (product_a, product_b) in conflict_list:
mps_with_productb = [mp for mp, p in enumerate(products) where p == product_b]
for mp1 in [mp for mp, p in enumerate(products) where p == product_a]:
model.AddLinearConstraint(sum(x[mp1,i,k] for i in shipping_dates for k in package_numbers) + sum(x[mp2,i,k] for mp2 in mps_with_productb for i in shipping_dates for k in package_numbers), 1, 1)


This will force only one of the variables to be 1, thus, for a given mini package mp1 which has product_a no other mini package which has product_b can be scheduled in the same package. If you do not have to ship all mini packages then change the first 1 to a 0.

• I think it can be close, however mini_Package (first dimension of x variable) is just a row number of the record, not a product code. Product codes for mini_Packages are available on another list. I edited my post to add short example. Could you have a look? Oct 14, 2019 at 10:50
• ok, so as I understand it the mini package corresponds to a certain product and the conflict list talks about products (not mini packages)... I'll try to incorporate it in the code. Oct 14, 2019 at 14:15
• Thank you for the update. I adjusted it a little bit to deal with project specifics, but the general idea worked well! :) Thx! Oct 21, 2019 at 19:02