1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    May 12 '20 at 13:11
  • $\begingroup$ 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 $\endgroup$
    – OR Junior
    May 12 '20 at 13:35
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – OR Junior
    May 12 '20 at 13:59
4
$\begingroup$

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

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

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}

$\endgroup$
10
  • $\begingroup$ 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$? $\endgroup$
    – RobPratt
    May 12 '20 at 14:01
  • $\begingroup$ @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$ $\endgroup$
    – OR Junior
    May 12 '20 at 14:04
  • $\begingroup$ another mistake and it was $\sum_j w_{i,j}$ $\endgroup$
    – OR Junior
    May 12 '20 at 14:06
  • $\begingroup$ OK, now you need to link $x$ and $w$. $\endgroup$
    – RobPratt
    May 12 '20 at 14:08
  • $\begingroup$ yes I will enforce $x_{i,j}=x_{k,j} \implies w_{i,j}+w_{k,j}=1$ as you taught me yesterday $\endgroup$
    – OR Junior
    May 12 '20 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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