5
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$
    – LarrySnyder610
    Commented Mar 20, 2020 at 19:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – LarrySnyder610
    Commented Mar 20, 2020 at 19:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sune
    Commented Mar 20, 2020 at 19:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Mar 20, 2020 at 22:06
  • 1
    $\begingroup$ A similar question asked here. (Reducing the number of suppliers for product portfolio) $\endgroup$
    – ooo
    Commented Mar 21, 2020 at 6:12

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.