# Expressing a chain of boolean ORs using ILP

How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables are binary.

For example, I would like to express $$x_1 \leq x_3$$ OR $$x_1 \leq x_4$$ OR $$x_1 \leq x_6$$. Notice the first variable in all the inequality constraints is $$x_1$$.

Derivation via conjunctive normal form: $$$$x_1 \implies \underset{i=2}{\overset n{\lor}} x_i \\ \neg x_1 \bigvee \underset{i=2}{\overset n{\lor}} x_i \\ 1 - x_1 + \sum_{i=2}^n x_i \ge 1 \\ x_1 \le \sum_{i=2}^n x_i$$$$

Your example constraint is equivalent to $$x_1 \le \text{max}(x_3,x_4,x_6)$$, which I will generalize to $$x_1 \le \max(x_2,\ldots,x_n)$$.

This max can be handled using section 2.6 "Logical OR" of FICO MIP formulations and linearizations: Quick reference.

Specifically, introduce a binary variable, $$d$$, to be constrained as follows so that it will be equal to $$\text{max}(x_2,\ldots,x_n)$$

\begin{align}d &\ge x_i, \quad i=2,\ldots, n\\d &\le \sum\limits_{i=2}^n x_i\end{align}

Now add the constraint: $$x_1 \le d$$.

• @TheSimpliFire Re: your edit. Centering constraints is o.k., but I prefer my dots at "ground level" rather than in the middle of the air. I think my way is far more common. – Mark L. Stone Aug 16 '19 at 15:54
• Right, changed from \cdots to \ldots, rather than ... – TheSimpliFire Aug 16 '19 at 15:54
• Note that if you are not interested in the variable $d$ itself, you can eliminate the variable to obtain $x_1 \le \sum_{i=2}^n x_i$ as in Rob Pratt's answer. – Kevin Dalmeijer Aug 16 '19 at 17:41
• @Kevin Dalmeijer Yes indeedy. – Mark L. Stone Aug 16 '19 at 17:42