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?

$\endgroup$
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$
  • $\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 at 22:51
  • 1
    $\begingroup$ They were entered simultaneously. $\endgroup$ – RobPratt Mar 27 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$
  • 1
    $\begingroup$ RobPratt's and @JBL's approach is better than mine. :) $\endgroup$ – LarrySnyder610 Mar 27 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 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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