4

We are dealing with a stochastic model and one of the constraints is \begin{align} y_j=\frac{\sum_{i \in I}\sum_{k \in K}\mathbb{E}\left[X_{ik}^2\right]x^k_{ij}}{\sum_{i \in I} \sum_{k \in K} \mathbb{E}\left[X_{ik}\right]x^k_{ij}}. \end{align} Here, decision variables are $y_j\geq 0$ and $x_{ij}^k$ which is binary and $X_{ik}$ is a random variable for which we know its mean and variance.

Is there a way to perhaps linearize this constraint? The only thing that came to mind for me was to use ${Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X]^2$, but this was not useful.

I would appreciate some hints so I try to solve it myself.

  • Do you also have constraints like $\sum_i x_{ij}^k=1$ or maybe $\sum_k x_{ij}^k=1$? – RobPratt Dec 17 '21 at 22:35
  • We have $\sum_j \sum_k x_{ij}^k=1$ for all $i$. Could you please let me know why this important? Is there another way to simplify the ratio? –  Dec 18 '21 at 04:03
  • I was thinking that you might be able to apply compact linearization a la Liberti. Where else does $y_j$ appear in the model? – RobPratt Dec 18 '21 at 04:33
  • Thank you. I'm looking it up now. The complete constraint that we modeled is $\mathbb{E}[Y_j]=(y_j z_j)/(1-z_j)$ for all $j$ and $z_j>0$, and we have $y_j$ as mentioned in the question. That is why I was trying to linearize the $RHS$ of $y_j$ by itself. –  Dec 18 '21 at 05:59

1 Answers1

6

Assuming the denominator cannot be zero (which would cause the known universe to implode) and that you can provide an upper bound for $y_j$, you can multiply both sides of the equation by the denominator. The new right side (the numerator) will be linear. The new left side will be $\sum_i \sum_k \mu_{ik} x_{ij}^k y_j$ (where $\mu$ is the mean of $X$). Now you just need to linearize the product $x_{ij}^k y_j$, which is a FAQ. See here for an answer.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Thank you. Is there a way to simplify the LHS by itself? –  Dec 18 '21 at 04:08
  • @prubin, Thanks for your useful answer. could you say please, how the new RHS might be linear if $\mathbb{E} X^2_{i,k}$ would be a variable? Is it replaced by its mean that is a parameter? – A.Omidi Dec 18 '21 at 07:56
  • 2
    @A.Omidi $X_{i,k}$ is a random variable, not a decision (model) variable. As noted by the author, the expectation of the square is the sum of the variance and the square of the mean, both of which I am assuming are parameters to the problem. – prubin Dec 18 '21 at 17:41
  • @ZiggyIggy I'm not sure what you mean. – prubin Dec 18 '21 at 17:42
  • @prubin, Many thanks for your explanation. – A.Omidi Dec 19 '21 at 04:55