- #1

- 177

- 24

I am tackling a problem related to the purchase of items that are available from different vendors, and from what I've seen so far it seems to me that it may be solvable by linear programming methods (I'm using R).

However I'm not sure how to set up the problem to achieve the exact goal I have in mind.

Can you please advise me on this?

Suppose you search for a few items you need to purchase, let's call them "a", "b" and "c".

You find that they are available at different vendors, called "x", "y" and "z".

Not all objects are available at all vendors, so in the end you have a table like this:

Item,Vendor,Price

"a","x",1

"a","y",1.5

"b","y",2

"b","z",1

"c","x",2

"c","y",0.5

You want to buy each item once and only once, so if all that matters is minimising the total price for the items, this is pretty simple to solve. You will buy "a" from "x", "b" from "z" and "c" from "y".

I know how to solve this in R.

The problem is different, though.

The shipping cost is charged per total order per vendor, so selecting many vendors may minimise the cost of the items, but not the total cost we pay.

E.g. if each vendor charges 5 for shipping costs, the total for the above order will be 1+1+0.5+5+5+5 = 17.5 .

If, on the other hand, you buy both "a" and "c" from "y", and "b" from "z", you have 1.5+0.5+1+5+5=13.

The total price for the items is greater, but the shipping cost is reduced, and the total is also significantly reduced.

Do you think it's possible to solve the minimisation of the total cost (items+shipping) using linear programming? Or can you suggest any other technique/package please?

The way I solved the 'easy' part (minimisation of the total price for the items) was by R package 'lpSolve', where the 'x' vector to find is a binary vector (0's and 1's) having length equal to the number of rows of the table (in this case 6). The coefficient vector is the Price column. The model.matrix function on the Item column gives you the constraint matrix, and the product of 'x' by this matrix must give a vector of 1's (each item is bought only once).

However, if I wanted to include the shipping cost, I wouldn't know how to do.

I can't sum it to the price of each item, because it is constant with respect to the number of items bought from one vendor.

I could make another model.matrix on the Vendor column, and I know the product of 'x' by this gives me a vector of the number of products bought from each vendor.

Here is where I get stuck; no idea how this information can be used in the minimisation of the total price.

I considered running the 'easy' part, getting all the item-price-optimal solutions (because in more complex cases there _are_ multiple solutions), calculating the total price for each solution and sorting.

Trouble is, today I submitted to this protocol a matrix of 492 rows with 20 vendors. I asked lpSolve to give me at most 100 solutions, thinking 'surely there won't be as many as that, given all the constraints'. No such luck. What was I thinking? When you have 2

^{492}possible vectors... I'm even amazed at how fast it ran!

Any help with this will be really appreciated.

Thanks!

L