6
$\begingroup$

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!

$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Brilliant! And do you know a way to enforce transitivity when there are more variables involved like in the last paragraph of my question? $\endgroup$ Commented Dec 20, 2020 at 23:33
  • $\begingroup$ See what I just added. About your last paragraph, I am sorry but I don't know what you call the "big M approach". I will look into Wikipedia, or maybe you have a reference ? $\endgroup$ Commented Dec 20, 2020 at 23:53
  • $\begingroup$ Here is an answer using the big M approach. Wikipedia's article on the subject is also good. $\endgroup$ Commented Dec 21, 2020 at 0:15
  • 1
    $\begingroup$ After doing some calculations of my own I think I have answered, starting from your answer, the question I asked in the last paragraph. I will post an answer of my own and choose your answer as the correct answer to my question. Please check if my answer is correct. $\endgroup$ Commented Dec 21, 2020 at 0:28
  • 1
    $\begingroup$ Regarding Excel's Solver performance, my intention is to make the final implementation in Python which I suppose can manage thousands of boolean variables. $\endgroup$ Commented Dec 21, 2020 at 0:29
2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ A remark: Restricting these constraints to cases $i<j<k$ is made possible by commutativity property $x_{i,j}=x_{j,i}$. $\endgroup$ Commented Dec 21, 2020 at 0:59
  • $\begingroup$ Thanks! That last line will be very helpful to make the program more efficient. Also, thank you Jean for the remark. $\endgroup$ Commented Dec 21, 2020 at 1:01
  • $\begingroup$ Note that could be obvious for some but it wasn't for me: for every value of i,j,k where i<j<k I had to add the following constraints: x_ij + x_jk - x_ik <= 1, x_ij - x_jk + x_ik <= 1, - x_ij + x_jk + x_ik <= 1 $\endgroup$ Commented Dec 25, 2020 at 18:27
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.