CODEWITHSUNDEEP
algorithm
Chris Evans
Chris Evans

Reputation: 993

Methods of comparing prices

I will create a list of products that I wish to buy. Let's say they are all given a unique reference code. I have a list of suppliers I can buy from and for convenience each supplier uses the same reference code for each product.

Some suppliers charge shipping. Others only charge shipping if you spend less than a certain amount. Some suppliers discount certain products if you buy them more than once but there may be restrictions (such as by 1 get 1 free).

It is extremely easy to take the list of products I want to buy and tally up the total it would cost to buy all of them from each supplier. What I want to do though is create a script to work out whether it would be better to split the order.

For example:

Retailer A charges:
Product A - £5
Product B - £10
Product C - £10
Product D - £10
Shipping - £5

Retailer B charges:
Product A - £5
Product B - £12
Product C - £12
Product D - £30
Shipping - £5 - free if spending £20 or more

In this case, if I wanted to buy Product C only, the cheapest would be from retailer A.

If I wanted to buy:
1x Product A
2x Product B
1x Product D

The cheapest would be retailer B (because of the free delivery) for products A and B and to then split the order and purchase product D from retailer A (as the price even with delivery is significantly lower even with delivery included).

So in my head it's not a complex task and I can work it out very easily on paper. The question is, how I would translate this into code. I'm not looking for the code to do it - just some guidance on the theory of how to implement it.

Upvotes: 4

Views: 3106

Answers (2)

user2566092
user2566092

Reputation: 4661

If we restrict the problem to simply choosing which vendor to buy each product from, and you get a vendor-dependent reduction in shipping cost if you spend a vendor-dependent amount, then you can formulate your problem as an integer linear program (IP or ILP), which is a good strategy for problems suspected to be NP-hard because there has been a lot of research and software packages developed that try to solve ILP fast in practice. You can read about linear programming and ILP online. An ILP problem instance has variables, linear constraints on the variables, and a linear objective you want to minimize or maximize. Here's the ILP set up for your problem:

For each product that a vendor sells, you have one vendor-product variable that tells how many of the product you will purchase from the vendor. For each of these variables you have a constraint that the variable must be >= 0. For each product you wish to buy, you have a constraint that the sum of all the vendor-product variables for that product must equal the total number of the product that you wish to buy.

Then for each vendor that offers a shipping discount, you have a shipping discount variable which will be either 0 if you don't get the discount, or 1 if you do. For each one of these shipping discount variables, you have constraints that the variable must be >=0 and <= 1; you also have a constraint that says when you multiply each vendor-product variable for the vendor by the vendor's price for that product, and add it all up for the vendor (so you get the total amount you are spending at the vendor), this amount is >= the vendor's shipping discount variable multiplied by the vendor's minimum amount you need to spend to get the discount.

You also have for each vendor a vendor variable which is 1 if you use the vendor, and 0 if you don't. For each of these vendor variables A, you have constraints 1 >= A > =0 and also for each vendor-product variable B for the vendor, you have a constraint A >= B/N, where N is the total number of items you want to buy.

Finally the objective you want to maximize is made by multiplying each vendor-product variable by the vendor's price for that product, adding it all up (call this part of the objective X), and then multiplying each vendor's shipping discount variable by the shipping cost reduction you get if you get the discount, adding it all up (call this part of the objective Y), and multiplying each vendor variable by the vendor's undiscounted shipping cost, adding it all up (call this part of the objective Z) then your objective is simply to minimize X - Y + Z. This is all you need to define the ILP, then you can feed it into an ILP solver and hopefully get a solution quickly.

Upvotes: 4

David
David

Reputation: 1136

Mixed Integer Linear Programming is ok for your problem.

You can use a free solver such as Coin Clp. If you want to know about commercial MILP solver performances, you can find some benchmarks there : http://plato.asu.edu/bench.html.

If you want to have a rough idea of the time required to solve your problem, you can run your problem on NEOS Server : http://www.neos-server.org/neos/.

When you have a lot of 0-1 variable, you can also contemplate to use Constraint Programming which often suits better for heavy combinatorial problems.

Both MILP and CP algorithms use branch and bound technique, which is faster than naive enumeration.

Cheers

Upvotes: 0

Related Questions