12
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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}

$\endgroup$
9
$\begingroup$

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

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

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.