Integer Linear Programming Conditional Constraints How can I create a constraint that reflects the following: if $x_{ij} = 1$ AND $x_{jk} = 1$ THEN $x_{ik} = 1$?
All my variables $x_{ij}$ are binary. To provide some context:
I'm trying to create a linear equation system to be solved via the simplex algorithm that provides a solution to the problems schools face when creating class groups. Each student chooses 5 other students that he would like to be with in the following year. The school promises that each student will be in a class with at least one of the students they chose. To create the equation system I decided that my variables will be boolean and represent the following: $x_{ij} = 1$ if student $i$ is with student $j$ and $x_{ij} = 0$ otherwise. Thus, $x_{ij}= x_{ji}$ and $x_{ii} = 1$.
However, I'm having trouble with the following constraint: if student $i$ is together with student $j$ and student $j$ is together with student $k$, then inevitably student $i$ will be together with student $k$. This is represented by the constraint I mentioned at the beginning of the question.
I tried using the big M approach as mentioned in other questions but to no avail. In these questions there was only one condition but I have two.
Even if I solve this problem, how can this be scalable? For example: if $x_{12} = x_{23} = x_{14} = 1$ then $x_{13} = x_{34} = x_{24} = 1$. Maybe the variables I chose are not correct and I'm overcomplicating things. If this is the case, any guidance in the right direction would be more than welcomed.
Thanks for the help in advance!
 A: 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...
A: 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$.
A: To try to answer the question I asked in the last paragraph and complement Jean Marie's very precise and helpful answer:
Let's continue with the example I put in my question: if $x_{12} = x_{23} = x_{14} = 1$  then $x_{13} = x_{34} = x_{24} = 1$.
Using the constraint $x_{ij} + x_{jk} - x_{ik} <= 1$ we have that:
$x_{13} = 1$
Moreover, as $x_{ij} = x_{ji}$: given $x_{12} = x_{14} = 1$, then $x_{24} = 1$
Finally, as we have that $x_{13} = 1$ and $x_{14} = 1$, then $x_{34} = 1$.
I know this is just an example and it does not prove anything, so if anyone finds proof to support that the constraint $x_{ij} + x_{jk} - x_{ik} <= 1$ is enough to represent all of the transitivity possibilities I would very much appreciate they post it as an answer.
