Price Comparison Methods

I will create a list of products that I want to buy. Say all of them are given a unique reference code. I have a list of suppliers that I can buy, and for convenience, each supplier uses the same code for each product.

Some suppliers charge shipping. Others pay only 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 (for example, 1 get 1 for free).

It is extremely easy to take the list of products I want to buy and calculate the total amount that it will cost to buy them from each supplier. What I want to do is create a script to determine if it would be better to break the order.

For instance:

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

Retailer B Expenses:
Product A - £ 5
Product B - £ 12
Product C - £ 12
Product D - £ 30
Shipping - £ 5 - free if costs are £ 20 or more

In this case, if I wanted to buy only product C, the seller A would be the cheapest.

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

The cheapest would be retailer B (due to free shipping) for products A and B, and then split the order and purchase product D from seller A (since the price even with delivery is much lower even with delivery).

So in my head this is not a difficult task, and I can easily process it on paper. The question is how I will translate this into code. I am not looking for code for this - just some recommendations on the theory of its implementation.

+4
source share
2 answers

If we limit the problem to simply choosing which supplier can buy each product, and you get a supplier-dependent reduction in shipping costs, if you spend a supplier-dependent amount, then you can state your problem as an integer linear program (IP or ILP) that is a good strategy for problems that are claimed to be NP-hard, because many studies and software packages have been developed that quickly solve the ILP problem in practice. You can read about linear programming and ILP on the Internet. An instance of an ILP problem has variables, linear constraints on variables, and a linear goal that you want to minimize or maximize. Here's the ILP configured for your problem:

For each product that the supplier sells, you have one supplier-product variable that tells you how much of the product you will buy from the supplier. For each of these variables, you have a restriction that the variable must be> = 0. For each product you want to buy, you have a restriction that the sum of all the supplier-product variables for this product must equal the total number of products, which you want to buy.

Then, for each supplier who offers a discount on delivery, you have a discount on delivery, which will be 0 if you do not receive a discount, or 1 if you do. For each of these delivery transfer variables, you have restrictions that the variable must be> = 0 and <= 1; you also have a restriction indicating when you multiply each supplier-product variable for a supplier by the supplier price for this product and add all this for the supplier (so that you get the total amount you spend on the seller), this is amount> = price seller discounts multiplied by the minimum supplier amount that you must spend to get the discount.

You also have a supplier variable for each provider, which is 1 if you use a provider, and 0 if you do not. For each of these supplier A variables, you have restrictions 1> = A> = 0, and for each supplier B variable for the supplier, you have restriction A> = B / N, where N is the total number of items you want to buy.

Finally, the goal you want to maximize is to multiply each supplier-supplier variable by the supplier price for this product, add it (call this part of object X), and then multiply each supplier’s delivery discount discount by the reduction in shipping costs that you receive. if you get a discount by adding all of this (name this part of object Y) and multiply each supplier variable by the undiscounted delivery cost of the supplier, adding all this (name this part of goal Z), then your goal is simply minimize X - Y + Z. That's all you need to determine the ILP, then you can submit it to the ILP solver and hopefully get a solution quickly.

+4
source

Mixed integer linear programming is right for your problem.

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

If you want to have a general idea of ​​the time it takes to solve your problem, you can run your problem on the NEOS server: http://www.neos-server.org/neos/ .

When you have a lot of variable 0-1, you can also use the Constraint Program, which is often better for severe combinatorial problems.

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

Greetings

0
source

Source: https://habr.com/ru/post/1490950/


All Articles