5

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.

Daniele
  • 91
  • 4
  • 1
    Hi, and welcome to OR.SE. Your question doesn't provide us with enough information to provide an answer. If you are asking how to formulate a certain constraint, then it's best if you can formulate the problem (minus your problematic constraint) and then say more clearly what you want the constraint to do. – LarrySnyder610 Mar 20 '20 at 19:07
  • 1
    When you say things like "it's better to buy as much as possible to reduce shipping costs", there are many ways to interpret (and formulate) that sort of idea. So please provide more specifics. Are there quantity discounts? Fixed costs? Are the costs linear? piecewise linear? nonlinear? etc. – LarrySnyder610 Mar 20 '20 at 19:08
  • 1
    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" ($y_j$) represent whether a supplier $j$ is chosen and the fixed cost be the shipping costs. The "allocation variables" ($x_{ij} $) 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. – Sune Mar 20 '20 at 19:18
  • Sorry guys, I'm going to fix the question! – Daniele Mar 20 '20 at 20:42
  • @Sune thank you very much !!! – Daniele Mar 20 '20 at 20:55
  • 3
    If shipping cost is linear with respect to spending, there are no economies or diseconomies of scale with respect to shipping. In that case, the optimal solution is to buy each item from the cheapest source, which is trivial. So I suspect there is something more to the problem. – prubin Mar 20 '20 at 22:06
  • No because not all sellers have all articles that you need. Maybe it's not clear, I'm going to add this detail. – Daniele Mar 20 '20 at 22:12
  • 1
    A similar question asked here. (Reducing the number of suppliers for product portfolio) – ooo Mar 21 '20 at 06:12
  • @anoopyadav thank you! but I think that in my case is a bit different because suppliers sell their articles at different prices – Daniele Mar 21 '20 at 11:49
  • You can take help from that formulation and try to build your own, and if you face any problem, you can ask here. – ooo Mar 21 '20 at 12:13
  • Rather than incorporating your (or @Sune's) answer into your question, it would be better for you (or @Sune) to post it as an answer. You can accept the answer if this is what solved your problem. – LarrySnyder610 Mar 26 '20 at 00:11
  • I posted my comment as an answer – Sune Mar 26 '20 at 11:40

1 Answers1

5

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" ($y_j$) represent whether a supplier $j$ is chosen and the fixed cost be the shipping costs. The "allocation variables" ($x_{ij}$) 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.

Sune
  • 6,457
  • 2
  • 17
  • 31