# Can we linearize the division of a binary variable by a continuous variable?

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.

• I think your idea with $M_r$ is good. You can now linearize $z_r \times x_{ry}$ like this : or.stackexchange.com/questions/39/… Feb 18, 2022 at 11:19
• You are using $r$ in two different ways in the same constraint: $\forall r$ and $\sum_r$ Feb 18, 2022 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$. Feb 20, 2022 at 13:53
• And your $\le 1$ constraint must be $=1$ to avoid division by zero. Feb 20, 2022 at 15:21

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$$
• 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$. Feb 21, 2022 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. Feb 22, 2022 at 6:43
• If the numerator is $0$, the (nonzero) denominator doesn’t matter. If the numerator is $1$, the denominator must be $d_r$. Feb 22, 2022 at 14:01