# Is it possible to do a linearization without introducing new variables?

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?

• 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? Sep 21 at 16:57
• 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. Sep 21 at 18:02

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}
• 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. Sep 21 at 18:13
• 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? Sep 21 at 20:17
• 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. Sep 21 at 20:36