9
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Oguz Toragay
    Mar 27, 2020 at 22:51
  • 1
    $\begingroup$ They were entered simultaneously. $\endgroup$
    – RobPratt
    Mar 27, 2020 at 22:52
9
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ RobPratt's and @JBL's approach is better than mine. :) $\endgroup$
    – LarrySnyder610
    Mar 27, 2020 at 23:33
  • 3
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Mar 28, 2020 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.