Does a linear expression exist for these ILP variables?

Question

I am formulating an integer linear program.

Suppose I have a set of binary variables $X_{i,j,k}$ that is $1$ if subject $i \in I$ is taught by lecturer $j \in J$ during timeslot $k \in K$, or $0$ otherwise.

This means, without additional refinement, $X_{i,j,k}$ will represent $|I|\times|J|\times|K|$ variables.

Now, suppose instead I have two set of variables $Y_{i,j}$ and $Z_{i,k}$ that is $1$ if subject $i \in I$ is taught by lecturer $j \in J$, or $0$ otherwise; and $1$ if subject $i \in I$ is run at timeslot $k \in K$, or $0$ otherwise, respectively.

If this works, these two sets represent $|I| \times (|J| + |K|)$ variables, which should be quite a lot less.

There is technically enough information here to work out at what timeslots $k \in K$ lecturer $j \in J$ is teaching, as you can "backtrack" from $Z$ to $Y$.

What I haven't been able to do, despite my best efforts, is to come up with a single, linear expression of $X_{i,j,k}$ in terms of $Y_{i,j}$ and $Z_{i,k}$. I'm beginning to doubt such an expression exists.

Answer 1

If subject $i$ is taught by lecturer $j$ and subject $i$ is run at timeslot $k$ ($Y_{i,j}=Z_{i,k}=1$), there are still two possibilities:

• either subject $i$ is taught by lecturer $j$ at timeslot $k$, which means $X_{i,j,k}=1$,
• or it is taught only taught by different lecturers at that time slot, which means $X_{i,j,k}=0$.

Therefore, without additional information, you cannot express $X_{i,j,k}$ as a function of $Y_{i,j}$ and $Z_{i,k}$ only.