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

Question

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?

Answer 1

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}