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: \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$.
\cdotsto\ldots, rather than...– ə̷̶̸͇̘̜́̍͗̂̄︣͟ Aug 16 '19 at 15:54