4
$\begingroup$

I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called MagicCardMarket, which is kind of an Ebay for trading cards. The problem is that the site doesn't have a proper optimization tool, so I'm trying to make it myself. (I found some other site that does this, but you have to pay for it and I'm learning a lot already doing it myself.)

The first thing I do is gather a bunch of information. The most important parts being how many and what cards the buyer want. Then I gather all the articles that comply with these cards and throw away all the bad ones (those who's quality is too bad, or language is incorrect, ...) Articles are basically instances of those cards being sold, with info about their seller and cost. So now I have a list of cards, and for each card a list of articles for those cards, and for each article a cost and seller (and from this seller I can get the shipping cost, this can depend on how many cards are bought from a single seller, though most of the time it stays almost constant.)

So now I'm looking for an algorithm to get all the cards you want, as cheap as possible. Taking into consideration that when I buy from more sellers, the shipping cost will go up.

Are there any algorithms I should look at, that might lend themselves to this problem very nicely? Or perhaps some general tips for these kinds of algorithms? It's the first time I'm trying to make this kind of algorithm, so I wasn't sure what to search for either.

The easiest way would probably be to just get all possible combinations, and check which is the cheapest, though most cards will have several hundreds of articles associated with them, and most of the time you'll have 60 to 80 cards you want to buy (a full deck.) So I don't think this is a good way, it uses enormous amount of ram and takes a lot of time. I'm also writing it as a web-app, preferably something that can also work on mobile phones.

Thanks a lot!

PS. I wasn't sure if this is the proper forum to ask this, please redirect me if I was wrong.

$\endgroup$
  • $\begingroup$ Say the shipping prices are obscene, compared to card prices. Then your problem is "find the least number of sellers who have all the cards needed". That is equivalent to set cover. Meaning that it is NP and thus you won't find a really fast solution. I'd suggest trying something like the greedy algorithm (mentioned in previous link). The result would not be optimal, but it might be good enough. $\endgroup$ – Karolis Juodelė Apr 20 '14 at 13:25
  • $\begingroup$ Well the thing is that costs of the cards range from 2 cents to €10-20, some going to 40. And then there are cards even more expensive than that. There's also the problem that some cards that go for 2 cents are sold by some for 10 to 50 cents, since not everyone is willing to go through the trouble of selling them for only 2 cents. But the set cover problem is very interesting. Thanks! $\endgroup$ – The Oddler Apr 20 '14 at 13:33
  • $\begingroup$ @KarolisJuodelė Fortunately it is in NP! ;) $\endgroup$ – Austin Buchanan Apr 20 '14 at 23:19
  • $\begingroup$ @TheOddler I was wishing for the same functionality on MCM. I would be happy to know if you plan to publish your algorithm. $\endgroup$ – john_leo Apr 22 '14 at 20:33
  • $\begingroup$ @john_leo Yes when it's finished I'll definitively will! I'll post it here too, so you can see ;) It might take some time still though, hopefully within the month. At least a beta version, without clean UI and stuff. If it works properly I do plan to create a proper GUI and stuff. Thanks for the interest, this motivates me a lot to do a good job at it :D $\endgroup$ – The Oddler Apr 23 '14 at 1:16
4
$\begingroup$

If you want to solve this in practice, I would suggest that you formulate it as an instance of integer linear programming (ILP).

You can have a variable $x_i$ for each article that is one if we buy the $i$th article, or $0$ otherwise. Now you get some constraints. For instance, if I want 2 of the Dreadlord card, and they're offered in the 3rd, 7th, and 8th articles, then I get the constraint that $x_3+x_7+x_8 \ge 2$. The objective function is your total cost. You want to minimize your total cost, subject to the requirements.

Here's how you can model the total cost. The only tricky bit are the shipping costs. For simplicity, assume that the shipping cost from a seller is fixed no matter how many items you buy from that seller. To help with modeling the shipping costs, introduce a variable $y_j$ for each seller, where $y_j=1$ if you buy anything from the $j$th seller and $y_j=0$ otherwise. Now use the "logical OR" construction from here to relate the $y_j$'s to the $x_i$'s. For instance, suppose that articles 4, 5, and 9 are from seller 2. Then you add the linear inequalities $y_2 \ge x_4$, $y_2 \ge x_5$, $y_2 \ge x_9$, $y_2 \le x_4 + x_5 + x_9$, $0 \le y_2 \le 1$. Do this for each seller. Now, the total cost is $$\sum_i c_i x_i + \sum_j c'_j y_j,$$ where $c_i$ is the per-item cost of the card in the $i$th article and $c'_j$ is the shipping cost of the $j$th seller. This is the objective function that you're going to try to minimize.

Then, throw an off-the-shelf ILP solver at the resulting set of constraints.

This problem is likely to be NP-hard, so in principle there might not be any efficient solution... but in practice ILP solvers are surprisingly good, so I bet they'll give you a pretty good solution to your problem.


Possible complications and details: If the seller has multiple copies of a card available, we need to modify the above. You can have $x_i$ count the number of them that you buy from that seller (instead of being 0 or 1). Also, we need to modify the construction of the $y_j$'s, as follows. For instance, if article 5 is from seller 2, and article 5 offers up to 17 copies of the Dreadlord card, then instead of $y_2 \ge x_5$, you should use $17 y_2 \ge x_5$ (this ensures that if $x_5 \ge 1$, then $y_2$ is forced to be $1$).

If the shipping cost is not constant per seller, then you might need a more complex model of the cost. However, here's one simple case that you can handle without difficulty. Suppose that the shipping cost for seller 2 is \$3 plus \$0.50 per card ordered. Then you can treat this as a fixed shipping cost of \$3 (regardless of how many cards are ordered), and increase the per-item cost of each card offered by that seller by \$0.50. If the shipping cost is a non-linear function of the number of cards bought, then you might need something fancier: in that case, you might want to ask a follow-up question about how to model that specific nonlinear function, and specify the nonlinear fucntion. Or, you could approximate the shipping cost by a linear function and solve the ILP problem anyway, to get something that might be close to optimal, even if your model isn't perfect.

$\endgroup$
  • $\begingroup$ This looks very interesting. I'm definitively going to look into this. Thanks! $\endgroup$ – The Oddler Apr 21 '14 at 13:05
  • $\begingroup$ I've been thinking about this, and although it should work, I can't figure out how to do the shipping costs. They should only be counted once, for any amount of cards bought from that seller. Any idea how to add that? (If it makes any difference, I'm currently using GLPK.) $\endgroup$ – The Oddler Apr 22 '14 at 18:30
  • $\begingroup$ @TheOddler, I've edited my answer to explain how to model the shipping costs. I hope this helps -- take a look and let me know if it's missing something. (GLPK should be fine. I've also used lp_solve and it also seems to work fine, too.) $\endgroup$ – D.W. Apr 22 '14 at 18:56
  • $\begingroup$ Wow. The logical-or construction is brilliant. I still have so much to learn. I don't think it's missing anything, your answer is pretty much perfect. The extra details at the end also help a lot. Thanks a bunch! $\endgroup$ – The Oddler Apr 22 '14 at 19: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.