# Is there a better way to formulate this constraint?

Let $$x_{r}^{j}=1\iff$$ the machine schedules job $$j$$ using resource $$r$$. My constraint says that: a resource cannot be used twice, i.e., if $$x_{r}^{j}=1$$, then $$x_{r}^{j'}=0$$ for $$j'\neq j$$. I write this as: $$x_{r}^{j}+x_{r}^{j'}\leq1,\forall j\neq j', \forall r.$$

Is there a better way to formulate this?

You can strengthen your "conflict" constraint to a "clique" constraint: $$\sum_j x_r^j \le 1$$ for all $$r$$. There are fewer of these, and they dominate the conflict constraints.

• What is the difference between your answer and the answer that was given before yours? I am asking because I can't see any difference in the both approaches. Am I missing something? Mar 27, 2020 at 22:51
• They were entered simultaneously. Mar 27, 2020 at 22:52

Same idea, but typically formulated as $$\sum_j x_r^j \leq 1, \: \forall r$$ For binary $$x$$

That seems like the right way to formulate it. There are lots of problems that use that sort of approach to ensure that at most one of two binary variables equal 1.

• RobPratt's and @JBL's approach is better than mine. :) Mar 27, 2020 at 23:33
• Those approaches dominate algebraically, but they also result in denser constraint matrices (albeit with fewer rows), so I'm not sure it's a lock that they are always preferable.
– prubin
Mar 28, 2020 at 19:00