1
$\begingroup$

There's multiple products and multiple buyers, each with their own quote for the product, and some not willing to buy the product at all. Some buyers require a minimum dollar amount for the order or they won't buy anything. I'm trying to find a series of equations or mathematical steps to take to find the most rewarding solution. I'm going to be using this solution on other sets of data like this set. Also, this will be done in a programming language, so the use of if/else statements is available, here (if a condition is true, do something, otherwise do something else). The highest price for each respective product is in bold in the example data in the image that is linked to below.

One example is that Buyer 7 won't accept the order if you just buy the three products in bold (the three times whose quotes are the highest with this buyer) because the minimum amount requirement in that case is $\$ $8. If you add Product 17 to Buyer 7's order, taking it away from Buyer 4, you'll exceed Buyer 7's requirements. This is a profitable move because now the total order for Buyer 7 exceeds what the total order for buyer 4 would have been (just the one product, at $\$ $7.25).

So I need to find a way to find possible profitable exchanges like this one. When there's a buyer whose requirements aren't meant, search for profitable exchanges by adding one or more products to that buyer's order, checking to see if it's more or less valuable than the sum of the orders it takes from.

Or, a more basic explanation: find the most profitable arrangement while taking into account the minimum requirements of the buyers.

I tried working on it and came up short (just did some basic arithmetic within the spreadsheet application, so I don't have any work to show, not that I would expect it to be useful). This problem is too overwhelming for me (almost as overwhelming as my lengthy explanation of it), so I'm seeking outside help. Anything that can help unravel the problem will be useful, and thank you in advance!

(I'll look at it again in the morning and see if I can make any progress, and post my results here in the comments. I think it's puzzle-like enough to earn the puzzle tag. This is my first question on Stack Exchange, so let me know if I've done anything wrong.)

Link to the Spreadsheet of problem data.

  • 0
    It looks like Robert Israel got it right. It feels like an NP-complete problem like knapsack. You might get some advantage by making a new list of buyers, each of whom bid on only one basket of goods with a price. Then you can incorporate shipping costs that vary with what products are bought, as the bid for (a and b) might not be the sum of the bids for a and b.2011-04-04

1 Answers 1

0

I hope I'm interpreting the problem correctly. Each item can go to at most one buyer; each buyer can either buy nothing at all or items with a total price at least that buyer's minimum; and subject to these constraints you want to maximize the total of the prices of the items sold.

This can be considered as an integer linear programming problem. Let $p_{ij}$ be the price of item $i$ for buyer $j$ (I'll take this to be 0 if buyer $j$ is not willing to pay anything for item $i$). Let $b_j$ be the minimum sale amount for buyer $j$. The variables will be $x_{ij}$ representing the number of item $i$ going to buyer $j$, and $m_j$ which will be 1 if buyer $j$ buys something and 0 if not. The problem is then

maximize $\sum_i \sum_j p_{ij} x_{ij}$

subject to

$\sum_j x_{ij} \le 1$ for each $i$

$\sum_i x_{ij} \le m_j$ for each $j$

$\sum_i p_{ij} x_{ij} \ge b_j m_j$ for each $j$

all $x_{ij}$ and $b_j$ \in $\{0,1\}$.