1
$\begingroup$

I have three binary variables $x_{i,j}^{m,r}$ , $y_i^{m,r}$, and $z_i^{m,r}$. There is another integer variable $w_i^r$. And I want to linearize the following logic:

$$ \sum_{m} x_{i,j}^{m,r} \ge 1 \implies w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r} \qquad \forall r, i, j $$

I think to linearize the above I need to introduce another binary. But could we do it without any new variables?

$\endgroup$
2
  • 1
    $\begingroup$ One small point, I don't believe this family of constraints should be quantified over all $m$. As currently written $m$ is sort of "doubly defined." (This was edited by @RobPratt.) As for your main question, it would be helpful to know more about your variables. For example, what is the range of $\sum_m y_i^{m,r}$? It would also be helpful to know why you want to avoid introducing variables, and what your overall goal is. Is this a program for a real-world application you are solving with a commercial solver? $\endgroup$ Sep 21, 2023 at 16:57
  • $\begingroup$ thanks for the heads up @NaturalLogZ yes $m$ was a mistake. but the summation for $y$ and $z$ is over $j$ not $i$, and their bound would be 0 to 1000. $\endgroup$
    – Rainbow
    Sep 21, 2023 at 18:02

1 Answer 1

6
$\begingroup$

You want to enforce $$\bigvee_m x_{i,j}^{m,r} \implies w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r} \quad \text{for all $r,i,j$}$$ Rewriting in conjunctive normal form leads to linear big-M constraints: \begin{align} \left(\lnot \bigvee_m x_{i,j}^{m,r}\right) \lor \left(w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r}\right) &&\text{for all $r,i,j$} \\ \left(\bigwedge_m \lnot x_{i,j}^{m,r}\right) \lor \left(w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r}\right) &&\text{for all $r,i,j$} \\ \bigwedge_{m'} \left(\lnot x_{i,j}^{m',r} \lor w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r}\right) &&\text{for all $r,i,j$} \\ \bigwedge_{m'} \left(x_{i,j}^{m',r} \implies w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r}\right) &&\text{for all $r,i,j$} \\ x_{i,j}^{m',r} \implies w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r} &&\text{for all $m',r,i,j$} \\ -M(1-x_{i,j}^{m',r}) \le w_j^r - w_i^r - \sum_{m} y_j^{m,r} + \sum_{m} z_j^{m,r} \le M(1-x_{i,j}^{m',r}) &&\text{for all $m',r,i,j$} \end{align}

$\endgroup$
4
  • $\begingroup$ Thanks a lot @RobPratt it was a new thing to learn for me! Could $m$ be equal to $m'$?? I only need to change index of y and z in summatins to j instead of i . Because that's the one I need in equality too. $\endgroup$
    – Rainbow
    Sep 21, 2023 at 18:13
  • 1
    $\begingroup$ Glad to help. Please mark my answer as accepted, and please edit your question to make any such corrections. $\endgroup$
    – RobPratt
    Sep 21, 2023 at 18:15
  • $\begingroup$ can you help me further @RobPratt. I kind of don't get the $m'$ in entirety. why in third line we need to have$m'$ and not use $m$ instead? Any resoan for that? $\endgroup$
    – Rainbow
    Sep 21, 2023 at 20:17
  • 1
    $\begingroup$ The $\bigwedge_m$ and $\sum_m$ have different scope, so when they first appeared together, I renamed the first $m$ to $m'$ to avoid collision. $\endgroup$
    – RobPratt
    Sep 21, 2023 at 20:36

Your Answer

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

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