6

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?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Clement
  • 2,252
  • 7
  • 13

1 Answers1

13

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Hi Rob Thank you very much! How do you see (check) that version (2) is a weaker formulation in comparison to version (1)? – Clement Jul 05 '21 at 07:46
  • 3
    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$. – SimonT Jul 05 '21 at 07:57
  • @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? – Clement Jul 05 '21 at 08:39
  • 1
    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. – SimonT Jul 05 '21 at 09:03
  • @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? – Clement Jul 05 '21 at 09:16
  • Maybe this would have the potential to be an entire new question. If you see stronger in the way of more fractional solutions are cut of you have to do a simple set containment proof. Let $A, B$ be the sets of feasible points of your two formulations then formulation $A$ would be stronger than $B$ if $A \subsetneq B$. – SimonT Jul 05 '21 at 09:33
  • @Rob: Rob, a somehow stupid/crazy/dared question comes into my mind. Is there a relatioship between conjuctive normal form and strength of an inequality? Is possibly, a constraint derived by the transformation into the conjuctive normal form, the strongest representation of this contraint? – Clement Jul 08 '21 at 08:25
  • @Clement It is a natural question because CNF often does yield strong formulations. I have seen examples where it does not, but I don't recall the details. Please open a separate question for this. – RobPratt Jul 08 '21 at 14:49
  • @Rob: Your answer suffices for my needs. I opened a question regarding the strength of inequalities but it is probably not well posed; the responses are not really satisfactory. The question is here: https://or.stackexchange.com/questions/6537/guides-for-strong-milp-formulations I think there is no need for a new one at least from my side. – Clement Jul 08 '21 at 20:09