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$.


2 Answers 2


Derivation via conjunctive normal form: \begin{equation} 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 \end{equation}


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$.

  • 2
    $\begingroup$ @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. $\endgroup$ Commented Aug 16, 2019 at 15:54
  • 1
    $\begingroup$ Right, changed from \cdots to \ldots, rather than ... $\endgroup$
    – TheSimpliFire
    Commented Aug 16, 2019 at 15:54
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Aug 16, 2019 at 17:41
  • $\begingroup$ @Kevin Dalmeijer Yes indeedy. $\endgroup$ Commented Aug 16, 2019 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.