0
$\begingroup$

I am trying to model the following constraint using binary variables $a$, $b$, $c$ and $d$:

$a$ will be true if at least one of $b$,$c$, or $d$ is true.

I know how to do $a$ if $b$ but I am having a very hard time introducing the "at least one of" part.

What I tried but realized didn't work is $a \leq b+c+d$ because this does mean $a$ can only be true if one of he others is true but it does not mean $a$ will be true if one of the others is true.

UPDATE: I just solved it! I did $a\geq b$,$a\geq c$,$a\geq d$. To show if any are $1$ (true) then $a$ must be as well.

$\endgroup$
0
$\begingroup$

HINT

  1. Learn how to define $x = b \text{ or } c$ .
  2. Similarly, define $y = x \text{ or } d$.
  3. Use the technique you mentioned you know to force $a$ if $y$.

UPDATE

What does $x \ge b$ enforce in the relationship between $x$ and $b$? What about $x \ge b$ and $x \ge c$ simultaneously?

$\endgroup$
  • $\begingroup$ Here is my take at this, please let me know if my logic is correct: $x \leq b+c$ and $y \leq x+d$ and $a=y$ where all the variables are binary $\endgroup$ – mhlzzz May 18 '17 at 20:43
  • $\begingroup$ @mhlzzz if you just want $b \text{ or } c \text{ or } d = 1 \implies a = 1$ then it's much simpler $\endgroup$ – gt6989b May 18 '17 at 20:46
  • $\begingroup$ @mhlzzz your solution does not force anything, in fact, if both $b,c$ are true, $x$ can be anything. See another update $\endgroup$ – gt6989b May 18 '17 at 20:48
  • $\begingroup$ Regarding your update, what I gather is that $x=1$ if $b=1$ or $c=1$ but if $b=0$ and $c=0$ then $x$ can be $0$ or $1$ $\endgroup$ – mhlzzz May 18 '17 at 20:52
  • $\begingroup$ @mhlzzz yes, i figured from your own answer you figured ot where i was leading you. $\endgroup$ – gt6989b May 19 '17 at 17:06
0
$\begingroup$

I did $a\geq b$,$a\geq c$,$a\geq d$. To show if any of $b$, $c$, or $d$ are $1$ (true) then $a$ must be as well.

$\endgroup$

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.