Binary Stochastic Programming with Independent or Positively Correlated Co-efficients

Question

1. A manufacturer can select a maximum of $N$ stores to fulfill orders from a total of $M$ stores who are looking for inventory, $N\le M$. The case when $N\geq M$ is trivially solved when all stores have positive demand.

2. When a store is selected, it is not known what the future contribution of that store will be to the manufacturer's revenue.

3. The contribution of a store $i$ to the manufacturer's revenue is a random variable, $A_{i}$, with cumulative distribution $F_{i}$ and density function $f_{i}$. This can thought of as a signal based on the demand or other factors.

4. $x_{i}$ is a binary variable that indicates whether the order from a particular store will be fulfilled or not.

5. A safe assumption seems to be that the revenue contribution random variables are independent or positively correlated since if one of them does well, we can expect others to do well. Negative correlation is assumed negligible by ruling out sabotage between stores and so on.

   • $A_{i}\sim F_{i}\left[0,u\right]$, $A_{i}$ is distributed according to the cumulative distribution $F_{i}$ over the interval $\left[0,u\right]$.
   • $F_{i},$ is increasing and has full support, which is the non-negative real line $\left[0,\infty\right]$.

   • $f_{i}=F_{i}',$ is the continuous density function of $F_{i}$.

   • $\forall i,j\quad F_{i,j}\left(a_{i},a_{j}\right)=F_{i}\left(a_{i}\right)F_{j}\left(a_{j}\right);\quad f_{i,j}\left(a_{i},a_{j}\right)=f_{i}\left(a_{i}\right)f_{j}\left(a_{j}\right)$, which means all the contribution random variables are independent.

THREE CASES ARISE

1) CASE ONE, REVENUE MAXIMIZATION

The manufacturer will try to maximize its revenue by fulfilling orders to stores that can make the biggest future contribution towards the same.

$$ \Pi_{U}^{*}=\underset{\left\{ ...,x_{i},...\right\} }{\max}E_{A_{i}}\left[\overset{M}{\underset{i=1}{\sum}}A_{i}x_{i}\right]\qquad\text{s.t.}\quad\overset{M}{\underset{i=1}{\sum}}x_{i}\leq N\;;x_{i}\in\left\{ 0,1\right\} $$

2) CASE TWO, MEAN VARIANCE OPTIMIZATION

The manufacturer will try to attain a certain level of revenue, $\bar{A}$, and minimize the variance, $\sigma^{2}\left(\Pi_{U}\right)$, by sending inventory to stores that can make the biggest future contribution towards the revenue while satisfying the variance criterion. Let, $\bar{A_{i}}=E\left[A_{i}\right]$, $\sigma_{i}^{2}=\text{Var}\left(A_{i}\right)$. $$ \sigma^{2}\left(\Pi_{U}\right)^{*}=\underset{\left\{ ...,x_{i},...\right\} }{\min}E_{A_{i}}\left[\overset{M}{\underset{i=1}{\sum}}\left(A_{i}-\bar{A_{i}}\right)^{2}x_{i}\right]\qquad\text{s.t}.\quad E_{A_{i}}\left[\overset{M}{\underset{i=1}{\sum}}A_{i}x_{i}\right]\geq\bar{A}\quad;\overset{M}{\underset{i=1}{\sum}}x_{i}\leq N\;;x_{i}\in\left\{ 0,1\right\} $$

3) CASE THREE, UNCERTAINTY ABOUT DELIVERY / ACCEPTANCE

Let $Y_{i}$ be a binary random variable that indicates whether a particular store that has been sent inventory will receive the inventory and accept to become a revenue contributor. We assume that this acceptance random variable is independent of the contribution random variable $A_{i}$. Any particular store will contribute to the manufacturer's revenue only if both $Y_{i}$ and $x_{i}$ are 1.

\begin{eqnarray*} \sigma^{2}\left(\Pi_{U}\right)^{*}=\underset{\left\{ ...,x_{i},...\right\} }{\min}E_{A_{i}}\left[\overset{M}{\underset{i=1}{\sum}}\left(A_{i}-\bar{A_{i}}\right)^{2}x_{i}Y_{i}\right]\\ \text{s.t}.\quad E_{A_{i}}\left[\overset{M}{\underset{i=1}{\sum}}A_{i}x_{i}Y_{i}\right] & = & \bar{A}\quad;\overset{M}{\underset{i=1}{\sum}}x_{i}\leq N\;;x_{i},\;Y_{i}\in\left\{ 0,1\right\} \\ \;;\Pr\left(Y_{i}=1\right)=p \end{eqnarray*}

There seems to be a deceptively simple solution as shown in the answer below, with an additional assumption.

Any suggestions / thoughts on whether this is correct and pointers to other solutions and /or reference material will be highly appreciated since I have only recently come across binary programming.

Question on Mathematics Forum without any answers: https://math.stackexchange.com/questions/1850628/binary-stochastic-programming-with-independent-or-positively-correlated-co-effic

Thanks in Advance,

Answer 1

1) CASE ONE, REVENUE MAXIMIZATION

A simple solution seems to be given by ordering all stores in descending order of expectations of their contributions to the revenue $...E\left[A_{i}\right]<E\left[A_{j}\right]...$ and picking the largest $N$ ones.

2) CASE TWO, MEAN VARIANCE OPTIMIZATION

If the revenue contribution random variables are independent or positively correlated, we can follow two solution threads.

• One, we can optimize this problem as if $x_{i}$ were a continuous function and select the $N$ stores with the largest weight.
• Alternately, we can simply pick $N$ stores with the largest ratio of their expected contribution to the standard deviation of the contribution. This is given by ordering all stores in descending order of the ratio of the expectations of their contributions to the standard deviation of their contributions $...\frac{E\left[A_{i}\right]}{\sigma_{i}}>\frac{E\left[A_{j}\right]}{\sigma_{j}}...$ and picking $N$ stores with the largest ratios.

Any suggestions / thoughts on whether this is correct and pointers to other solutions and /or reference material will be highly appreciated since I have only recently come across binary programming.