5
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Hi Rob Thank you very much! How do you see (check) that version (2) is a weaker formulation in comparison to version (1)? $\endgroup$
    – Clement
    Jul 5 at 7:46
  • 3
    $\begingroup$ The formulation is weaker in the sense that less fractional solutions are cut off. For example the fractional combination $x_1=.9, x_2=x_3=0, y=0.3$ is valid in (2) but not in (1). On the other hand (1) always implies (2) by summing up the constraints and dividing by $3$. $\endgroup$
    – SimonT
    Jul 5 at 7:57
  • $\begingroup$ @SimonT But will such a combination ever be proposed by a LP-Solver? This is not a vertex of the feasible region defined by the inequalities. What is it that I don't get right? $\endgroup$
    – Clement
    Jul 5 at 8:39
  • 1
    $\begingroup$ It might be a vertex together with some other constraint. But if you adjust my example from above to $x_1=1, x_2=x_3=0, y=\frac{1}{3}$ it is also a vertex of only the constraints from your question. $\endgroup$
    – SimonT
    Jul 5 at 9:03
  • $\begingroup$ @SimonT: Yes, you are right. I just displayed the feasible region in Mathematica (x1 => y, x2 => y vs x1 + x2 => 2 y). In version (2) vertices with fractional valued coordinates are shown, while this is not the case for version (1). Now, it is in general not possible to draw the feasible region defined by a set of constraints; so is there a way to prove that a set of constraints is stronger than another? Instead, do rules exist that ensure that a model is strong? $\endgroup$
    – Clement
    Jul 5 at 9:16

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.