1
$\begingroup$

I have the ambition to build an application that determents the best set of orders.

Let's say I'm an postage-stamp collector. And I have certain postage-stamps on my wish list. On the secondhand-market are many sellers selling my desired stamps. The sellers originate from around the world. Some offer the postage-stamp for an extremely low price, but since they are selling from (for example) India, the shipping cost on the one stamp is enormous. Others offer the stamp for an average price, but are close-by and have less shipping costs. The interesting thing about postage-stamps is that they are extremely lightweight. A lot of them fit together in one shipment without increasing the price of the shipment (until some point). Last but not least, not every seller is selling all possible stamps. Since they are collectors them selfs, they can only sell what they own.

Shipment costs are based on weight, but since all postage-stamps weigh the same (roughly) we price them by amount:

  • 0-3 stamps cost \$1.10 to ship.
  • 3-4 stamps costs \$2.00 to ship.
  • 5+ stamps costs \$3.00 to ship.

I want to buy the following stamps (wish list):

  • SuperRareStamp
  • NotSoRareStamp
  • ThisIsAnOldStamp
  • MyFirstPostHereStamp
  • ExampleStamp

The following sellers are active on the secondhand-market:

Freddy the big Seller, who is selling:

  • SuperRareStamp for \$5.00
  • NotSoRareStamp for \$1.00
  • ThisIsAnOldStamp for \$3.00
  • MyFirstPostHereStamp for \$0.50
  • ExampleStamp for \$2.00

Annick, who is selling:

  • NotSoRareStamp for \$1.00
  • MyFirstPostHereStamp for \$0.50

Eddy, who is selling:

  • SuperRareStamp for \$5.50
  • NotSoRareStamp for \$1.00
  • ThisIsAnOldStamp for \$2.00
  • ExampleStamp for \$1.50

Results:

  • Buying everything at Freddy the big Seller costs: \$11.50 + \$3.00 shipping = \$14.50

  • Buying both stamps at Annick, and fill the rest with Eddy costs: \$1.50 + \$1.10 Shipping (Annick) + \$10.00 + \$1.10 Shipping (Freddy) = \$13.70

  • Buying everything at Eddy, and the MyFirstPostHereStamp from Annick costs: \$10.00 + \$2.00 Shipping (Eddy) + \$0.50 + \$1.10 Shipping (Annick) = \$13.60

Output: Although Eddy is selling the SuperRareStamp for the highest price, it's still the smarter choice to buy the stamp from him.

Sidenote: Different sellers can (in the real world) have different shipping price tiers. I'm interested in how would that be used in a formula.

Problem sizes (as requested): Items on the wishlist: never more than 100, Number of sellers 20000, Number of distinct stamps sold per seller range (1-120000).

$\endgroup$
  • 1
    $\begingroup$ I don't understand your problem. What is the input, and what is the required output? Please include both a formal description and some examples. $\endgroup$ – Yuval Filmus Apr 5 '18 at 9:08
  • $\begingroup$ @YuvalFilmus As far as I can see, there is a (probably implicit) list of items. The input is a list of sellers, each offering a price on each item and each having a shipping cost. The output is a set of orders (e.g., "Buy A and C from 1; B from 2") that includes every item and that minimizes total cost, including shipping. $\endgroup$ – David Richerby Apr 5 '18 at 9:33
  • 2
    $\begingroup$ This is just a guess – the OP should describe the problem more clearly before anybody attempts to solve what they conjecture to be the problem. $\endgroup$ – Yuval Filmus Apr 5 '18 at 9:37
  • 1
    $\begingroup$ In addition to the other feedback, it'd be helpful to tell us whether this is a practical problem (you care about time to solve it in practice) or a theoretical problem (you care about the asymptotics of the worst-case running time). If it's a practical problem, it might be helpful to give us a rough idea of the problem sizes you are likely to encounter (number of sellers, number of products). I encourage you to edit the question to provide this additional information and clarifications. And welcome to CS.SE! $\endgroup$ – D.W. Apr 5 '18 at 18:20
  • 1
    $\begingroup$ Also, you're not asking any question. $\endgroup$ – Raphael Apr 7 '18 at 9:26
1
$\begingroup$

Your problem is NP-hard (and so NP-complete), by reduction from vertex cover. Given a graph, we associate with each edge 10 stamps, and with each vertex a seller who sells all stamps for some fixed price which is the same for all sellers and stamps.

Since there are 10 stamps per edge, for every solution there is an equivalent solution (having the same cost) in which all stamps are bought from the same seller. Minimizing the price is thus the same as minimizing the number of sellers, which is the same as finding a vertex cover of minimum size for the original graph.


What this means is that you'll have to use a heuristic algorithm. Which heuristic to use depends on the problem size and other properties. For example, if there is only a small number of stamps or sellers, then it might be feasible to "try out all options", pruning away options which are strictly worse than others.

One simple heuristic is local search. Start with the solution which completely ignores shipping costs. Then try to find small modifications which reduce the total price. This could perhaps be feasible if implemented in a smart way.

$\endgroup$
  • $\begingroup$ Thank you for providing both a theoretical answer as well as pointing out a practical approach for a possible solution. I will have to read-up on some of the terms you mentioned before I can post a more in-dept comment. $\endgroup$ – Gert-Jan Bos Apr 7 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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