5

I'm trying to solve an MINLP problem where the following division term is appearing in the objective: $$z_r = \frac{x_{ry}}{\sum_r d_r x_{ry}}, \forall r, y,$$ where $x_{ry}$ is a 2D binary variable and $d_r$ is a non-zero real number. In addition, there is a constraint $\sum_r x_{ry} \leq 1$. Is there a suitable way to linearize this division?

I tried to use a new variable $M_r = z_r \times \sum_r d_r x_{ry}$, but the situation is still the same for the commercial solvers.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Sourav Mondal
  • 95
  • 3
  • 1
    I think your idea with $M_r$ is good. You can now linearize $z_r \times x_{ry}$ like this : https://or.stackexchange.com/questions/39/how-to-linearize-the-product-of-a-binary-and-a-non-negative-continuous-variable – Kuifje Feb 18 '22 at 11:19
  • 2
    You are using $r$ in two different ways in the same constraint: $\forall r$ and $\sum_r$ – RobPratt Feb 18 '22 at 14:05
  • Agree. Instead, we can use $x_y = \sum_r d_r x_{ry}$, but the problem is still the same, i.e., $z_r = \frac{x_{ry}}{x_y}, \forall r,y$. – Sourav Mondal Feb 20 '22 at 13:53
  • And your $\le 1$ constraint must be $=1$ to avoid division by zero. – RobPratt Feb 20 '22 at 15:21

1 Answers1

8

You want to linearize \begin{align} z_r &= \frac{x_{ry}}{\sum_s d_s x_{sy}} &&\text{for all $r$ and $y$} \tag1 \\ \sum_s x_{sy} &= 1 &&\text{for all $y$} \tag2 \end{align}

  • If $x_{ry}=0$, then $(1)$ implies that $z_r=0$.
  • If $x_{ry}=1$, then $(1)$ and $(2)$ imply that $z_r=1/d_r$.

So you can linearize $(1)$ by replacing it with $$z_r=x_{ry}/d_r \quad \text{for all $r$ and $y$} \tag3$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Thanks for your useful answer. Would you say please, is there any preference to linearize such division by conic reformulation, specifically, SOCP than other methods like what you mentioned? – A.Omidi Feb 21 '22 at 07:25
  • 2
    I would be very surprised if there is a better reformulation than what I proposed in my answer, but it is worth trying. – RobPratt Feb 21 '22 at 15:34
  • Glad to help. Notice that $x_{ry}=d_r z_r$, so it doesn't depend on $y$. Is that expected in your problem? If so, probably better to just drop the $y$ index: $x_r$. – RobPratt Feb 21 '22 at 16:26
  • No, $y$ is needed. Basically, $x_{ry}$ indicates if $r$ is associated with $y$, like in an assignment problem. However, now I'm seeing a small problem with the denominator being replaced with $d_r$. The sum indicates the total $d_r$ of all the $r$'s associated with $y$, which we do not know beforehand. – Sourav Mondal Feb 22 '22 at 06:43
  • If the numerator is $0$, the (nonzero) denominator doesn’t matter. If the numerator is $1$, the denominator must be $d_r$. – RobPratt Feb 22 '22 at 14:01