Formulating constraints to an integer programming problem

101 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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.

6
On

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?