Search code examples
phpalgorithmcombinationsmathematical-optimization

Find highest total price by selling items to multiple buyers, limited by user input to how many separate sales can be made

EDIT: Im sorry guys my explantion of the problem wasn't clear! This should be better:

  1. User sends ID numbers of articles and the max. number of bundles(packages)

  2. API searches for all prices available for the articles and calculates best result for min. number of bundles (limit to max. number provided by customer) ONE Bundle is one package of items delivered to ONE platform(buyer)

Thanks!

Solution

  • This is a fun little problem. I spent a few hours on it this morning, and while I don't have a complete solution, I think I have enough for you to get started (which I believe was what you asked for).

    First of all, I'm assuming these things, based on your description of the problem:

    • All buyers quote a price for all the items
    • There's no assumption about the items, they may all be different
    • The user can only interact with a limited number of buyers
    • The user wants to sell every item, each to one buyer
    • The user may sell multiple items to a single buyer

    Exact solution -- brute force approach

    For this, the first thing to realize is that, for a given set of buyers, it is straight forward to calculate the maximum total revenue, because you can just choose the highest price offered in that set of buyers for each item. Add up all those highest prices, and you have the max total revenue for that set of buyers.

    Now all you have to do is make that calculation for every possible combination of buyers. That's a basic combinations problem: "n choose k" where n is the total number of buyers and k is the number of buyers you're limited to. There are functions out there that will generate lists of these combinations (I wrote my own... there's also this PEAR package for php).

    Once you have a max total revenue for every combination of chosen buyers, just pick the biggest one, and you've solved the problem.

    More elegant algorithm?

    However, as I intimated by calling this "brute force", the above is not fast, and scales horribly. My machine runs out of memory with 20 buyers and 20 items. I'm sure a better algorithm exists, and I've got a good one, but it isn't perfect.

    It's based on opportunity costs. I calculate the difference between the highest price and the second highest price for each item. That difference is an opportunity cost for not picking the buyer with that highest price.

    Then I pick buyers offering high prices for items where the opportunity cost is the highest (thus avoiding the worst opportunity costs), until I have k - 1 buyers (where k is the max I can pick). The final choice is tricky, and instead of writing a much more complicated algorithm, I just run all the possibilities for the final buyer and pick the best revenue.

    This strategy picks the best combination most of the time, and if it misses, it doesn't miss much. Its also scales relatively well. It's 10x faster than brute force on small scales, and if I quadruple all the parameters (buyers, buyer limit, and items), calculation time goes up by a factor of 20. Considering how many combinations are involved, that's pretty good.

    I've got some code drafted, but it's too long for this post. Let me know if you're interested, and I'll figure out a way to send it to you.