Take the 2-minute tour ×

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.

share|improve this question
@Cameron: The character $ is used to enter "math mode" to typeset formulas, which is why you had formatting problems. I've fixed them. –  Arturo Magidin Apr 3 '11 at 2:03
@Cameron: There are a number of work-arounds; the one I like is to type $\$$, which will produce a single $ sign. –  Arturo Magidin Apr 3 '11 at 2:06
As written, there seems to be confusion between buyers and sellers. At the start of the second paragraph, "Buyer 7 won't accept the order..." but usually sellers accept orders. I think that whole paragraph needs a look regarding buyer/seller. Even the spreadsheet looks confused (compared to my expectation) on this, as the buyers have a minimum sale. Usually buyers don't care about minimum sales, they just want the cheapest basket of products. Please explain. –  Ross Millikan Apr 3 '11 at 3:07
Interesting problem. It sounds like it would have applications to the stock market. –  Carl Brannen Apr 3 '11 at 7:04
@Ross: It's a rather unique scenario in which buyers could lose money if the item(s) they're buying isn't profitable enough to justify shipping costs, which the buyers cover. These products are to be resold by the buyers, and their quotes are based on estimated demand and resale value. I hope that clears the problem up for you. –  user9028 Apr 4 '11 at 2:32
show 1 more comment

1 Answer

up vote 0 down vote accepted

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\}$.

share|improve this answer
add comment

Your Answer

