5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Kuifje
    Feb 18, 2022 at 11:19
  • 2
    $\begingroup$ You are using $r$ in two different ways in the same constraint: $\forall r$ and $\sum_r$ $\endgroup$
    – RobPratt
    Feb 18, 2022 at 14:05
  • $\begingroup$ 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$. $\endgroup$
    – Sourav Mondal
    Feb 20, 2022 at 13:53
  • $\begingroup$ And your $\le 1$ constraint must be $=1$ to avoid division by zero. $\endgroup$
    – RobPratt
    Feb 20, 2022 at 15:21

1 Answer 1

Reset to default
8
$\begingroup$

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$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Feb 21, 2022 at 7:25
  • 2
    $\begingroup$ I would be very surprised if there is a better reformulation than what I proposed in my answer, but it is worth trying. $\endgroup$
    – RobPratt
    Feb 21, 2022 at 15:34
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Feb 21, 2022 at 16:26
  • $\begingroup$ 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. $\endgroup$
    – Sourav Mondal
    Feb 22, 2022 at 6:43
  • $\begingroup$ If the numerator is $0$, the (nonzero) denominator doesn’t matter. If the numerator is $1$, the denominator must be $d_r$. $\endgroup$
    – RobPratt
    Feb 22, 2022 at 14:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.