Integer Linear Programming Conditional Constraints

Question

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!

Answer 1

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...

Answer 2

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.

Answer 3

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