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
    Commented 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
    Commented 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
    Commented Feb 20, 2022 at 13:53
  • $\begingroup$ And your $\le 1$ constraint must be $=1$ to avoid division by zero. $\endgroup$
    – RobPratt
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 22, 2022 at 14:01

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