Ideas on how to approach the construction of a probability-heavy algorithm

Question

Definitions

Assume we have a Shopping List $L$ which is a list of pairs of Items and Quantities: $L = [(i_1, Q_1), (i_2, Q_2), (i_3, Q_3) ...$

We also have a Stock List $S$ which is a list of pairs of Containers and Prices: $S = [(C_1, p_1),(C_2, p_2), (C_3,p_3)...]$

Each container is a list of 3-tuples of Items, Quantities, and Probabilities: $C_n = \left[\left(t_1,q_1,\frac{a_1}{b_1}\right), \left(t_2,q_2,\frac{a_2}{b_2}\right), \left(t_3,q_3,\frac{a_3}{b_3}\right)...\right]$

Purchasing a container for a given price gives you a chance of getting each item within it. The chance is equal to each item's probability. The probabilities are independent of each other (two items with a probability of 1/2 are treated as two coin flips, it isn't "one or the other"), and their quantities are absolute. If we had $C_1 = \left[\right(x, 2, \frac{1}{2}\left)\right]$, then there is a one-in-two chance of getting two $x$s, and no chance of getting only a single $x$.

The Goal

I'm trying to come up with some algorithm which has the ultimate goal of satisfying a given shopping list from some stock list. Due to the random nature of the problem, it is impossible to construct a definite chain of purchases to make. Thus, I was thinking that foo(L, S) should return the best next purchase -- the container to buy which satisfies the most items in the shopping list for the lowest price. Purchasing this container can affect the shopping list in a variety of ways, so upon purchasing, the list will be run through the algorithm again and again until it is empty.

My Attempts

If I could construct a function which outputs some "instantaneous value" of each container, I could then calculate and sort each container by this value and purchase the one highest-valued one.

This value of a container would be its benefit minus its cost. Calculating the cost of containers which contain only one needed item is simple enough, but I'm stumped on containers with multiple items. Consider this example:

$L = [(x, 1), (y, 1)]$

$S = \left[\\ \left(\left[\left(x, 1, \frac{1}{2}\right)\right], 10\right),\\ \left(\left[\left(y, 1, \frac{1}{2}\right)\right], 10\right),\\ \left(\left[\left(x, 1, \frac{1}{3}\right),\left(y, 1, \frac{1}{3}\right)\right], 20\right)\\ \right]$

(The first container costs \$10 and has a 1/2 chance of giving an $x$. The second container costs \$10 and has a 1/2 chance of giving a $y$. The third container costs \$20 and has a 1/3 chance of giving an $x$, and a 1/3 chance of giving a $y$.)

The cost of getting an $x$ from the first container is \$20. This would satisfy one out of two of our list's requested items. If our strategy for satisfying the list was to brute-force the first container, then the second, the total cost of the list would be \$40.

What gives me trouble is that third choice. There is a 1/9 chance of spending only \$20 and getting both of our $x$ and $y$ in one move. There is a 4/9 chance of spending \$20 and getting either our $x$ or $y$ -- we could then get the remaining one for \$20 and be done for \$40. Finally, there is another 4/9 chance of getting nothing.

I suspect that the best path in this case is to buy the third container until at least either an $x$ or $y$ is obtained, then buy the remaining one from the first or second container. (Edit: A simulation shows that solely buying containers 1 and 2 leads to an average cost of \$40 to satisfy the list, as expected, but buying the third container then one or two leads to an average cost of \$52 to satisfy the list. Besides simulating, I'm unsure of how to derive that 52)

Any ideas on how to approach this?

Answer 1

One plausible approach would be to use integer linear programming. The following won't be optimal, but it might be decent.

We could try to find quantities $x_1,x_2,\dots$ for the containers, so that if we buy that many containers, the expected number of each item is at least the desired quantity. This leads to an integer linear program, with one inequality per item

$$\sum_i x_i q_{i,j} p'_{i,j} \ge Q_j$$

where $q_{i,j}$ is the number of item $j$ in container $i$, and $p'_{i,j}$ is the corresponding probability. Then, we want to minimize $\sum_i x_i p_i$, the total price of these containers, where $p_i$ is the price of the $i$th container. You could use an off-the-shelf ILP solver to solve for the $x_i$'s, or as a heuristic, use a linear programming solver and ignore that the $x_i$'s need to be integers.

Then, you could randomly sample a container, with container $i$ sampled with weight proportional to $x_i$. This is a heuristic, but it might help identify which container you most want to buy, so it might work well enough in practice.

You shouldn't expect any efficient algorithm that gives the optimal solution; this problem is NP-hard, by reduction from the knapsack problem.