Find the best way to buy p Product from limit x Vendors

Question

I have to buy 100 Products ( or p Products) from 20 Vendors ( or v Vendors). Each Vendors have all of these Products, but they sell different Price.

I want to find the best price to get 100 Products. Asume that there is no Shipping Cost. There are v^p ways. And I will get only one way that have best Price. The problem seem to be easy if there is no requirement: LIMIT number of Vendors to x in the Orders because of Time Delivery ( or Some reasons).

So, the problem is: Find the best way to buy p Product from limit x Vendors ( There are v Vendors , x<=v).

I can generate all Combination of Vendors( There are C(v,x) combinations) and compare the Total Price. But There are so many combinations . (if there are 20 Vendors, there are around 185k combinations). I stuck at this idea. Someone has same problem , pls help me. Thank you very much.

Answer 1

This problem is equivalent to the non-metric k-center problem (cities = products, warehouses = vendors), which is NP-hard.

I would try mixed integer programming. Here's one formulation.

minimize c(i, j) y(i, j)  # cost of all of the orders
subject to
for all i: sum over j of y(i, j) = 1  # buy each product once
for all i, j: y(i, j) <= z(j)  # buy products only from chosen vendors
sum over j of z(j) <= x  # choose at most x vendors
for all i, j: 0 <= y(i, j) <= 1
for all j: z(j) in {0, 1}

The interpretation of the variables is that i is a product, j is a vendor, c(i, j) is the cost of product i from vendor j, y(i, j) is 1 if we buy product i from vendor j and 0 otherwise, z(j) is 1 is we buy from vendor j at all and 0 otherwise.

There are many free mixed integer program solvers available.

Answer 2

Not Correct as shown by @Per the structure lacks optimal substructure

My assumptions are as follows, from the master table you need to create a sub list which has only "x" vendor columns, and "Best Price" is the "Sum" of all the prices.

Use a dynamic programming approach What you do is define two functions, Picking (i,k) and NotPicking(i,k). What it means is getting the best with ability to pick vendors from 1,.. i with maximum of k vendors.

Picking (1,_) = Sum(All prices)
NotPicking (1,_) = INF
Picking (_,0) = INF
NotPicking (_,0) = INF

Picking (i,k) = Min (Picking(i-1,k-1) + NotPicking(i-1,k-1)) - D (The difference you get because of having this vendor)
NotPicking (i,k) = Min (Picking(i-1,k) + NotPicking(i-1,k))

You just solve it for a i from 1 to V and k from 1 to X

You calculate the difference by maintaining for each picking the whole product list, and calculating the difference.