Better way to formulate these constraints?

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?

• What's wrong with the formulation you already have? I don't see how anyone could answer the question with either a "yes" (how would we know that some other formulation is better? there are no rules that guarantee that anyone formulation is better than another) or "no" (for the same reason), so the question doesn't seem likely to be answerable to me.
– D.W.
Sep 24 '18 at 0:20
• @D.W. I thought that a formulation with many constraints like mine is not good that's why.
– zdm
Sep 24 '18 at 13:52
• It's not clear to me why you thought that.
– D.W.
Sep 24 '18 at 14:47
• Because the complexity of the problem will increase as the number of constraints increases. A "better" formulation to me is one that uses fewer constraints and fewer variables if possible.
– zdm
Sep 24 '18 at 15:03

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