Return to Question

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers at different prices.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.

======================= SOLUTION by @Sune =======================

You can formulate this (depending on whether you have more constraints you haven't mentioned) as an uncapacitated facility location problem. Let the "location variables" (yj) represent whether a supplier j is chosen and the fixed cost be the shipping costs. The "allocation variables" (xij) represent if an item i is sourced from supplier j or not, and the allocation cost represents the cost of the item at the given supplier.

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers at different prices.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers at different prices.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers at different prices.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.

======================= SOLUTION by @Sune =======================

You can formulate this (depending on whether you have more constraints you haven't mentioned) as an uncapacitated facility location problem. Let the "location variables" (yj) represent whether a supplier j is chosen and the fixed cost be the shipping costs. The "allocation variables" (xij) represent if an item i is sourced from supplier j or not, and the allocation cost represents the cost of the item at the given supplier.

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items).

The items can be purchased from many sellers at different prices.

Sellers have a subset of your articles. (It's unlikely that a seller has all article you need.)

All the sellers have the same shipping cost and this is linear respect to the spending.

I know that this is an Integer Linear Programming problem, but I'm unable to express the shipping constraint in the canonical ILP form.

My Operations Research professor told me that this is a sub partition problem, but I don't know what is.

In an average use case there are about 100 articles to purchase.