Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Let $y, x_1, x_2, x_3$ be binary variables.
The following holds: $y=1 \implies x_1=1, x_2=1, x_3=1$
I can model this by requiring (1) \begin{align}x_1 &\ge y\\x_2 &\ge y\\x_3 &\ge y\end{align}
or by requiring (2) $$\frac{x_1 + x_2 + x_3}3 \ge y$$
The question is, is requirement (1) or requirement (2) more advantageous and why?
Version (1) arises from conjunctive normal form as follows: $$ y \implies (x_1 \land x_2 \land x_3) \\ \lnot y \lor (x_1 \land x_2 \land x_3) \\ (\lnot y \lor x_1) \land (\lnot y \lor x_2) \land (\lnot y \lor x_3) \\ (1 - y) + x_1 \ge 1 \land (1 - y) + x_2 \ge 1 \land (1 - y) + x_3 \ge 1 \\ x_1 \ge y \land x_2 \ge y \land x_3 \ge y $$
Version (2) is an aggregation of (1) and yields a smaller but weaker linear formulation.
State-of-the-art MILP solvers will generate the useful constraints in (1) from (2) dynamically as cuts, so you are probably better off with the smaller LP. But it is worth trying both ways.
Also, I recommend writing (2) as $x_1+x_2+x_3 \ge 3y$ so that you have integer coefficients. Division by 3 would introduce infinitely repeating decimals that must be approximated unless you are using an exact solver.
