# Using big M values for a constraint

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?

• Your formulation instead enforces $$x_{i,j}=x_{k,j}\implies z_k<z_i<z_k.$$ In other words, you have an AND where you want an OR. – RobPratt May 12 '20 at 13:11
• Yes, thank you, I got it Dr, .. I really need if $z_i \neq z_k$ then $z_i > z_k$ OR (not AND) $z_i < z_k$ .. I will think of it again – OR Junior May 12 '20 at 13:35

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 ...

• I use Gurobi with Matlab .. so you can imagine ! – OR Junior May 12 '20 at 7:48
• With CPLEX you can use logical constraints with Matlab as can be seen in the example foodmanu.m – Alex Fleischer May 12 '20 at 8:06
• The problem in Gurobi with Matlab we write the whole model as one matrix, not even like Gurobi with any other platforms – OR Junior May 12 '20 at 8:14

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$$.

• thank you for your continuous and extreme support .. I have used another approach and posted it .. please tell me if it is right or the error in it or.stackexchange.com/a/4116/3480 – OR Junior May 12 '20 at 13:59

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}

• Your first constraint uses $i$ in two different ways. Also, there is no connection with $x$ and the other variables. Do you have bounds on $z$? – RobPratt May 12 '20 at 14:01
• @RobPratt sorry it was a mistake I modified it .. I mean $\sum_j$ not $\sum_i$ .. and z is integer from $0$ to $z_n$ – OR Junior May 12 '20 at 14:04
• another mistake and it was $\sum_j w_{i,j}$ – OR Junior May 12 '20 at 14:06
• OK, now you need to link $x$ and $w$. – RobPratt May 12 '20 at 14:08
• yes I will enforce $x_{i,j}=x_{k,j} \implies w_{i,j}+w_{k,j}=1$ as you taught me yesterday – OR Junior May 12 '20 at 14:10