Integer Linear Programming Conditional Constraints

Transitivity can be handled in the following way:

$$(1−x_{i,j}) + (1−x_{j,k}) \ge (1−x_{i,k})\tag{1}$$

as explained for example in paragraph $2.2$ of this reference.

I would like to add that (1), expressed under the equivalent form:

$$x_{i,j}+x_{j,k}-x_{i,k} \leq 1$$

possesses an equivalent logical formulation (have you some practice of Prolog language ?) under the following "Horn clause":

$$\lnot x_{i,j} \lor \lnot x_{j,k} \lor x_{i,k}$$

(see pages 11 and 12 of this reference ).

Remark: nothing surprizing in fact because this clause expresses the fact that:

$$x_{i,j} \ \& \ x_{j,k} \ \implies \ x_{i,k}$$

I have personnally been programming with Prolog ; unlike its reputation (under the condition to use good implementations like SWI-Prolog), it can be an efficient alternative for working on boolean variables if one hasn't too much of them...


You can obtain the constraint via conjunctive normal form as follows: $$ (x_{i,j} \land x_{j,k}) \implies x_{i,k} \\ \lnot (x_{i,j} \land x_{j,k}) \lor x_{i,k} \\ \lnot x_{i,j} \lor \lnot x_{j,k} \lor x_{i,k} \\ (1- x_{i,j}) + (1- x_{j,k}) + x_{i,k} \ge 1 \\ x_{i,j} + x_{j,k} - x_{i,k} \le 1 $$ You need only enforce these constraints for $i < j < k$.