2
$\begingroup$

This is a weird optimization problem I recently came across which I cannot solve.

Suppose we start off with an empty container of M&Ms. We take and add M&Ms to the container every year for $n$ years. The number of M&Ms I take out each year, $B$, is always the same (think of it as a parameter). The number added in year $i$, $A(i)$, is known (think of it as data).

If $A(i) - B < 0$, I have an M&M "bank" I can go to cover my losses and so I can keep operating even with a deficit. We let $D(0)$ represent the initial amount in the bank and $D(i)$ denote the amount in the bank in year $i$, where we calculate $D(i)$ as: $D(i) = D(i-1) + A(i) - B$, if $A(i) - B <= 0$; $D(i) = \min(D(0), D(i-1) + A (i) - B)$, if $A(i) - B > 0$ (in the latter case, I throw away any extra M&Ms left over after I cover my debt to the bank).

The problem is: "Find the maximum value of $B$ such that $D(n) = D(0)$" (i.e., what is the maximum number of M&Ms I can take out every year, so I have no deficit with the bank at the end of the $n$ years?).

1 Answers 1

1

Since you can't store extra M&Ms, and you can't be in debt to the bank at the end, your constraint is basically that, for each year $i$, there have to be more M&Ms going in than M&Ms going out from year $i$ through year $n$. This gives rise to the following linear programming formulation of your problem:

$ \begin{align} \text{Maximize } &B \\ \text{subject to } &\sum_{k=i}^n (A_i - B) \geq 0, \text{ for each }i \in \{1,2,\ldots,n\}, \\ &B \geq 0. \end{align} $ This problem is simple enough that you don't even need an LP solver. Rewrite the constraint as $\begin{align} &\sum_{k=i}^n A_i \geq B(n-i+1), \text{ or } \\ &B \leq \frac{1}{n-i+1}\sum_{k=i}^n A_i. \end{align}$ Thus the solution is $B = \min_{1 \leq i \leq n} \left\{\frac{1}{n-i+1}\sum_{k=i}^n A_i\right\}.$ If $B$ is required to be an integer, then you'll need to round this expression down to the nearest integer.

  • 0
    @MattBrenneman: You're welcome. :)2011-11-20