4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you also have constraints like $\sum_i x_{ij}^k=1$ or maybe $\sum_k x_{ij}^k=1$? $\endgroup$
    – RobPratt
    Commented Dec 17, 2021 at 22:35
  • $\begingroup$ 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? $\endgroup$
    – user9659
    Commented Dec 18, 2021 at 4:03
  • $\begingroup$ I was thinking that you might be able to apply compact linearization a la Liberti. Where else does $y_j$ appear in the model? $\endgroup$
    – RobPratt
    Commented Dec 18, 2021 at 4:33
  • $\begingroup$ 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. $\endgroup$
    – user9659
    Commented Dec 18, 2021 at 5:59

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. Is there a way to simplify the LHS by itself? $\endgroup$
    – user9659
    Commented Dec 18, 2021 at 4:08
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Commented Dec 18, 2021 at 7:56
  • 2
    $\begingroup$ @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. $\endgroup$
    – prubin ♦
    Commented Dec 18, 2021 at 17:41
  • $\begingroup$ @ZiggyIggy I'm not sure what you mean. $\endgroup$
    – prubin ♦
    Commented Dec 18, 2021 at 17:42
  • $\begingroup$ @prubin, Many thanks for your explanation. $\endgroup$
    – A.Omidi
    Commented Dec 19, 2021 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.