How to model this chain of logical implication

Question

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

For instance $\omega_{xy}$ might indicate precedence, i.e., $x$, $y$ being the nodes $x$ and $y$, respectively. Thus if $\omega_{xy}$$=1$, it implies that the departure time of the 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 $z$, which also to be visited as is always behind temporally, and for other nodes that are also temporally behind $z$, such as $z_1...z_n$

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

$\omega_{xy}$$=1$ $\implies$ $\omega_{xz}$$=1$

$\omega_{xy}$$=1$ $\implies$ $\omega_{xz_1}$$=1$

...

$\omega_{xy}$$=1$ $\implies$ $\omega_{xz_n}$$=1$

Appreciate your kind guidance.

Thank you!

Which are variables and which are constants? What types are the variables? — RobPratt, Nov 16 '20 at 13:53
What's the difference between the first two implications (assuming $x$ and $y$ are both variables)? — LarrySnyder610, Nov 16 '20 at 14:42
In any case, see whether this answers your question: https://or.stackexchange.com/q/76/38 — LarrySnyder610, Nov 16 '20 at 14:43
Hi, I have just edited my question. Sorry for the prior unclear description. Thank you! — Mike, Nov 17 '20 at 02:29

score 3 · Accepted Answer · answered Nov 17 '20 at 03:04

3

To enforce $x = 1 \implies y = 1$ for binary variables $x$ and $y$, impose linear constraint $x \le y$. You can derive this constraint via conjunctive normal form: $$ x \implies y \\ \lnot x \lor y \\ (1 - x) + y \ge 1 \\ x \le y $$

answered Nov 17 '20 at 03:04

RobPratt

32,006
1
44
84

Thanks! Guess I overcomplicated stuff myself. – Mike Nov 17 '20 at 03:06

How to model this chain of logical implication

1 Answers1