[Solved]: Card-buying algorithm

Problem Detail: 

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.

Asked By : The Oddler

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23950

3.2K people like this

 Download Related Notes/Documents