Algorithm to find best solution

Question

I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve: A Company makes a new contract with a customer and wants to order materials. There are serval suppliers with fix delivery costs. Each supplier can offer some of the materials with different pack sizes and prices. What is the best approach to get the materials for the lowest price? I wanted my App to automatically suggest the best order.

* You can order at multiple suppliers; You can order more materials than needed *

Further explanation: I know what materials needed for the contract, for Example (Input):

750 of Material 1 250 of Material 2 500 of Material 4 50 of Material 5

I know the delivery Costs and material costs of each supplier. Delivery costs are only paid once for each supplier. I want to get the best solution to order the materials (cheapest).

Output should be a list like: Ammount - Product of supplier - Supplier

Example:

Material 1

1 x 500Q,P40 from Supplier 1 2 x 125Q,P12 from Supplier 3

Material 2

1 x 250Q,P60 from Supplier 3

....

Answer 1

Your problem is hard, but not too hard.

Start with a subproblem: For one material, you have various package sizes with different cost. You also require a certain amount of material. Find the cheapest way to buy your material.

To do that, use dynamic programming: Let's say you need 5000 units. Find in turn the cheapest way to buy at least 1, 2, 3, ..., 5000 units. The cheapest way for 0 units is buying nothing. To buy at least K units, you either buy one package with size >= K, or you buy one package with size k < K, then buy packages with total size at least K - k at the lowest possible price. Of the choices you have, you use the cheapest one.

Second subproblem: Find all sets of possible suppliers. Just try all possible subsets - for n suppliers there are $2^n$ possible subsets of suppliers, and reject all subsets that don't contain any supplier for a material that is required.

Then for each possibe subset of suppliers, find the cheapest way to buy each material. Add up the cost for the materials, plus the delivery cost. And then take the subset of suppliers that was cheapest.

For small problem sizes, this shouldn't take too long. Of course the problem looks NP-complete if you turn it into a decision problem, so your execution time will grow exponentially with the problem size.

Finding the cheapest way to buy each material seems to be the most time critical. Think how you can optimise it by finding packages you should never buy (if you have a pack of 25 costing 12, and a pack of 24 costing 13, you would never buy the 24), and amounts you don't care about (in your example with pack sizes 100, 200 and 500, your total is always a multiple of 100).

Answer 2

Your problem is NP-hard. Note that I'm slightly changing definitions here, since the original problem is an optimization problem and not a decision problem. More specifically, I will assume your problem is a decision problem where we want to decide if you can make an order that is below a cost $C$. I will now assume that there is a hypothetical subroutine Order-Cost that runs in polynomial time that solves this.

We can reduce Set Cover to your problem fairly easily. Let $U$ be the universe of elements, let $\mathcal{X}$ be the set of subsets of $U$. We are also given an integer $k$. We now want to decide whether there exist (at most) $k$ sets in $\mathcal{X}$ with their union being equal to $U$.

For each $X \in \mathcal{X}$, we create a supplier with a delivery cost of 1. For each $x \in X$ we make a material with only one quantity and price, where the quantity is equal to 1 and its price to 0. Furthermore, we set $C = k$. For our order we want to have at least all elements of $U$.

Note that this reduction runs in polynomial time as we go over each set of $\mathcal{X}$ and element of $U$ once. We return whatever Order-Cost returns.

Proof of correctness: Suppose a Set Cover instance is a yes instance, then let $S$ be the set of sets that unify to $U$. Note that $|S| \leq k$. Since the constructed suppliers directly correspond to the sets in $\mathcal{X}$, we can buy all items from our order $U$ with cost at most $k$. Hence, Order-Cost also outputs yes.

The other direction is extremely similar. If we can find at most $k$ suppliers, that is we pay at most $k$, to complete our order, then there exist $k$ sets such that their union is $U$.

Since your problem is NP-hard, finding an efficient algorithm will be hard. You can attempt a backtrack algorithm, where you go over each material and vendor. Although since there is a touch of subset sum involved, even that will become rather complicated.