Lowest value from multiple possibles

Sorry about the title. Not sure what to call this question.

I am trying to calculate the lowest total cost of lets say a box, circle and square over n amount of suppliers. Each supplier charges a delivery charge for any order. (Very difficult to explain so here's an example)

Supplier   A       B     C
Box        10      7      1
Circle      7      9     11
Square     10      8     12
Delivery    5      6      6


If I were to order a single box, circle and square from each supplier, the total order would be

Total      32     30     30


So clearly I would order it from B or C.

However! If I were to order a box from C and the rest from A, then (1 + 6) + (7 + 10 + 5) = 29. So I would be saving myself £1.

The way I figured that out was good ole AAA, BBB, CCC, AAB, AAC, ABC, ACB etc etc and to compare the final result of each selecting the lowest, but I figure there must be a formula out there!?

Some other factors to take into consideration:

• Delivery is dependent on weight, the heavier the order, the more the delivery charge. so 5kg = £5, 10kg = £10. So it may be that ordering two items from supplier A actually causes double the delivery rate.
• There may be more than one of an item, for example, 2 circles, 1 box, 3 squares.
• One supplier might not have all items, for example, supplier C might not have any squares.
• An item may have to be split over suppliers. For example, you want 10 boxes but each supplier only has 5

Welcome to my nightmare :(

-
complex-analysis is a well defined branch of mathematics which deals with functions of complex numbers. Please read the description before choosing to use the tag. Your problem is possibly more algorithmic than "formulaic". Also, the "some other factors" part of the question needs to be made precise before someone can answer your question. –  Aryabhata Apr 10 '12 at 20:31
Thanks Henning and Aryabhata –  Christian Apr 10 '12 at 21:06
As pointed out by Robert Israel, this is an integer linear programming problem (which is in general NP-hard), but there is very simple $O(2^nnk)$ algorithm: consider every subset of suppliers and calculate minimum for it (and calculating minimum is easy, you just sum the delivery cost of the suppliers in the considered subset and use the cheapest price for every object from available suppliers). –  dtldarek Apr 10 '12 at 23:11

This can be done using integer linear programming.

-

An answer to "Looking for an answer drawing from credible and/or official sources."

Linear programming (whole chapter): http://www.cs.berkeley.edu/~vazirani/algorithms/chap7.pdf

Integer linear programming (there is a paragraph there): http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf

To show that it can be done using integer linear programming, I will consider just your example. Just set $ordBox$, $ordCir$, $ordSqr$ to your how much boxes, circles and squares you want and minimize (but just in integer domain) $paymentA+paymentB+paymentC$ with respect to the following constraints:

\begin{align*} ordBox &= boxA + boxB + boxC \\\ ordCir &= cirA + cirB + cirC \\\ ordSqr &= sqrA + sqrB + sqrC \\\ paymentA &= 5*usesA + 10*boxA + 7*cirA + 10*sqrA \\\ paymentB &= 6*usesB + 7*boxB + 9*cirB + 8*sqrB \\\ paymentC &= 6*usesC + 1*boxC + 11*cirC + 12*sqrC \\\ 0 &\leq usesA \leq 1 \\\ 0 &\leq usesB \leq 1 \\\ 0 &\leq usesC \leq 1 \\\ 0 &\leq boxA \leq ordBox*usesA \\\ &\ldots \\\ 0 &\leq sqrC \leq ordSqr*usesC \\\ \end{align*}

Naturally, this is not a proof that your problem can't be done in polynomial time (unless $P = NP$). To create simple $O(n2^nk)$ algorithm just consider every subset of suppliers, and if the suppliers are fixed just run the trivial greedy algorithm which chooses the cheapest option from available sources (this runs in $O(nk)$ time). I won't write any pseudocode, because it would be an overkill.

-
"Looking for an answer drawing from credible and/or official sources" was the closest match to asking for "the answer as a formula" the other options were way off... but i like your answer so far :) –  Christian Apr 14 '12 at 18:14

I don't know if you are interested in theoretical results, but it may be interesting to someone else.

The decision problem is $NP$-hard: take an instance of the boolean satisfiability problem over the variables $x_1,\dots, x_n$. $$P(x):\quad\bigwedge_{i=1}^p \bigvee_{j\in J_i} x_j$$ (with $J_i\subseteq\{1,\dots,n\}\cup\{-1,\dots,-n\}$ and the convention $x_{-j}=\neg x_j$).

To encode the fact that $x_i \vee \neg x_i$ is always true, we define $J_{p+i} = \{i,-i\}$ for $i=1,\dots,n$.

We define a supplier selection problem over $2n$ suppliers $\{1,\dots,n\}\cup\{-1,\dots,-n\}$ and $p+n$ products. Let the cost of product $i$ when ordered from supplier $j$ be $c_{i,j}=0$ if $j\in J_i$ and $c_{i,j}=1$ otherwise. Let the shipping cost of supplier $j$ be $s_j=1$.

Then the supplier selection problem is the minimum of $f$ over all 0,1-valued $x$: $$f(x) = \sum_{|j|=1}^n x_j s_j + \sum_{i=1}^{p+n} \min_{\substack{j\\x_j\ne 0}} c_{i,j}$$

We always have $f(x)\ge n$ as for each $j=1,\dots,n$, either we have to pay 1 in shipping to $j$ or $-j$, or we have to pay 1 for product $p+j$ since we can't order it from $j$ or $-j$.

If $P$ is satisfied by $x$, we have $f(x)=n$ as we pay $n$ in shipping and all products are free. Conversely if $f(x)=n$, any minimal superset $x'$ of $x$ (viewed as a set of suppliers) such that for all $j$, $x'_j \vee x'_{-j}$ is true will satisfy $f(x')\le f(x)=n$. Therefore since we pay $n$ total shipping, we never have $x'_j=x'_{-j}=1$ (otherwise we would pay more shipping) so $x'$ is a valid boolean assignment, and all the products are free (otherwise we would pay more in total): thus $P$ is satisfied by $x'$.

So since the problem is $NP$-complete (even when you restrict all product and shipping costs to $\{0,1\}$), there is no formula or efficient algorithm, and there is no hope of doing much better than to use integer linear programming, as was suggested by others.

ILP also allows you to model your additional constraints: you can express the fact that a supplier has limited stock, or that shipping cost is higher if more than a certain number of items is ordered.