Using big M values for a constraint

Question

I want to enforce $x_{i,j}=x_{k,j}\implies z_i \neq z_k$ where $k = i-1$ so I used \begin{align}z_k + 1 - (x_{i,j} - x_{k,j})) \leq z_i \leq z_k - 1 - (x_{i,j} - x_{k,j})\quad\text{for each $j$}\end{align} as $x$ is an integer variable where $x \in \{{0,1}\}$ and $z$ is an integer.

I tried this on an example but I kept getting errors for the $z$ values \begin{align} x_{1,1} = 0, &&x_{1,2} = 1,\\ x_{2,1} = 0, &&x_{2,2} = 1, \\ x_{3,1} = 1, &&x_{3,2} = 0, \\ x_{4,1} = 1, &&x_{4,2} = 0, \\ \text{and }&&1 \leq z\leq 2 \end{align} so \begin{align} z_1 + 1 - (x_{2,1} - x_{1,1})) &\leq z_2 \leq z_1 - 1 - (x_{2,1} - x_{1,1})\\ z_1 + 1 - (x_{2,2} - x_{1,2})) &\leq z_2 \leq z_1 - 1 - (x_{2,2} - x_{1,2})\\ z_2 + 1 - (x_{3,1} - x_{2,1})) &\leq z_3 \leq z_2 - 1 - (x_{3,1} - x_{2,1})\\ z_2 + 1 - (x_{3,2} - x_{2,2})) &\leq z_3 \leq z_2 - 1 - (x_{3,2} - x_{2,2})\\ z_3 + 1 - (x_{4,1} - x_{3,1})) &\leq z_4 \leq z_3 - 1 - (x_{4,1} - x_{3,1})\\ z_3 + 1 - (x_{4,2} - x_{3,2})) &\leq z_4 \leq z_3 - 1 - (x_{4,2} - x_{3,2}). \end{align}

What is the error?

Answer 1

Introduce three binary variables $y_{i,k,s}$, where $s\in\{1,2,3\}$, to indicate whether $z_i < z_k$, $z_i = z_k$, or $z_i > z_k$, respectively. The constraints are then: \begin{align} \sum_s y_{i,k,s} &= 1 \tag1 \\ z_i + 1 - z_k &\le M_1(1-y_{i,k,1}) \tag2 \\ -(1-y_{i,k,2}) \le x_{i,j} + x_{k,j} - 1 &\le 1-y_{i,k,2} \tag3\\ z_k + 1 - z_i &\le M_3(1-y_{i,k,3}) \tag4 \end{align} Constraint $(1)$ selects one of the three cases. Constraint $(2)$ enforces $y_{i,k,1} = 1 \implies z_i < z_k$. Constraint $(3)$ enforces $y_{i,k,2} = 1 \implies x_{i,j} + x_{k,j} = 1$, which is the same as $x_{i,j} \ne x_{k,j}$ because $x$ is binary. This is the contrapositive of your desired implication. Constraint $(4)$ enforces $y_{i,k,3} = 1 \implies z_i > z_k$.

Answer 2

in CPLEX with all APIs you can use logical constraints that will help you to model that:

dvar int x;
dvar int y;
dvar int z;
dvar int t;

subject to
{
  (x==y) => (z!=t);
}

in OPL for instance. But you can write the same with C++, java, python ...

Answer 3

Thank to Dr @RobPratt I think the answer will be to introduce a binary variable $w_{i,j}$ to indicate whether $z_i=j$. in other words to enforce $x_{i,j} = x_{k,j} \implies w_{i,j} + w_{k,j} = 1 $ while \begin{align} \sum_j w_{i,j} &= 1 &&\text{for all $i$}\\ \sum_j j w_{i,j} &= z_i &&\text{for all $i$}\\ \end{align}