# 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 '19 at 7:07