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

Appreciate your kind guidance.

Thank you!


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, privacy policy and cookie policy

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