Better way to formulate these constraints?

Question

I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:

• If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j'\neq j$.
• If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j$ at time $t'\neq t$ using processor $k'\neq k$.

In other words, both constraints say that once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine.

For the first constraint, I write it as $x_{ijt}^k+x_{ij't'}^{k'}\leq 1$, for all $i,j'\neq j, k, k',t,t'$.

For the second constraint, I write it as $x_{ijt}^k+x_{ijt'}^{k'}\leq 1$, for all $i,j, k\neq k',t\neq t'$.

Can I improve this formulation?

Answer 1

Here is a different way to formulate the situation, which is simpler conceptually and which might be implemented more easily, although the number of variables is still the same (which can be not reduced fundamentally, anyway).

"Once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine". It looks like it is assumed that a processor is attached to the same machine regardless of the job or time. That means there is only one degree of freedom about the variable $j$ and $k$.

Let us use a new index $p=(j,k)$ to denote a pair of machine and a processor on it. Let binary variable $x_i^{pt}$ be $1$ iff job $i$ is assigned to processor $p$ at time $t$ (the index $t$ and $p$ is put together since they represent the resources). Then we can express the constraints as a single inequality, $$x_i^{pt}+x_i^{p't'}\leq 1\quad \text{ for all }p\neq p',t,t', i$$

In the actual programming, we can pack $j$ and $k$ side by side to form $p$ as the union structure in C/C++. For example, let $p$ be a 32-bit unsigned integer whose upper 16 bits is $j$ and whose lower 16 bits is $k$. We can also use a hash table with $p$ as keys and $(j,k)$ as values.

Answer 2

If your measure of "better" is number of variables or number of constraints, I don't believe it is possible to do better. You obviously can't use fewer variables as all of them are already defined; your formulation hasn't added any new variables. You have one inequality per constraint, so I don't see how you would expect to have fewer inequalities.