I would like to seek some advice on modeling the following (chain of) logical implication:

For instance $\omega_{xz}$ might indicate precedence, i.e., $x$, $z$ being the nodes $x$ and $z$, respectively. Thus if $\omega_{xz}$$=1$, it implies that the departure time of a vehicle from node $x $ is to be less than or equal to the arrival time at node $y$.

Say for instance, there is an additional node $y_1$, which must visited after $x$ temporally, and for other nodes that are also temporally behind $y_1$, such as $y_1...y_n$, i.e $x$ is the first node to be visited followed by $y_1...y_n$.

If $z$ is before $x$, $z$ must definitely be visited before $y_1$, followed by $y_2$ and so on

Hence, I would like to force the logical implication such that

$\omega_{zx}$$\ge$ $\omega_{zy_1}$ $\implies$ $\omega_{zx}$$\ge$ $\omega_{zy_2}$

$\omega_{zx}$$\ge$ $\omega_{zy_1}$ $\implies$ $\omega_{zx}$$\ge$ $\omega_{zy_3}$


$\omega_{zx}$$\ge$ $\omega_{zy_1}$ $\implies$ $\omega_{zx}$$\ge$ $\omega_{zy_n}$

on the other hand the converse might also be true such If $y_n$ is before $z$, $y_1$ be visited before $z$. As the chain of nodes could either be on the extreme left or extreme right of $z$.

$\omega_{y_nz}$$\le$ $\omega_{y_{n-1}z}$ $\implies$ $\omega_{y_nz}$$\le$ $\omega_{y_{n-2}z}$

$\omega_{y_nz}$$\le$ $\omega_{y_{n-1}z}$ $\implies$ $\omega_{y_nz}$$\le$ $\omega_{y_{n-3}z}$


$\omega_{y_nz}$$\le$ $\omega_{y_{n-1}z}$ $\implies$ $\omega_{y_nz}$$\le$ $\omega_{xz}$


1 Answer 1


You can use conjunctive normal form to derive the desired constraints. The first one is: $$a \ge b \implies a\ge c\\ (b \implies a) \implies (c \implies a)\\ \lnot(\lnot b \lor a) \lor (\lnot c \lor a)\\ (b \land \lnot a) \lor (\lnot c \lor a)\\ (b \lor \lnot c \lor a) \land (\lnot a \lor \lnot c \lor a)\\ (b \lor \lnot c \lor a)\\ b+ 1- c +a \ge 1\\ a+b \ge c $$

The second one is: $$a \le b \implies a\le c\\ (a \implies b) \implies (a \implies c)\\ \lnot(\lnot a \lor b) \lor (\lnot a \lor c)\\ (a \land \lnot b) \lor (\lnot a \lor c)\\ (a \lor \lnot a \lor c) \land (\lnot b \lor \lnot a \lor c)\\ \lnot b \lor \lnot a \lor c\\ 1-b + 1-a + c \ge 1\\ a+b \le c+1 $$

  • $\begingroup$ Thank you very much! $\endgroup$
    – Mike
    Nov 18, 2020 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.