Aganippe76

Answered

2022-07-07

I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.

I will explain what I mean precisely: Lets say I have a set of inequalities $e{q}_{1}$ to $e{q}_{n}$, which must hold. But, additionally, I have several more inequalities $eq{a}_{1},....,eq{a}_{k}$ and $eq{b}_{1},...,eq{b}_{k}$, that can be partitioned to couples (of the form $\u27e8eq{a}_{i},\phantom{\rule{thinmathspace}{0ex}}eq{b}_{i}\u27e9$ for all $1\le i\le k$), such that either $eq{a}_{i}$ holds or if it doesn't then $eq{b}_{i}$. Nonetheless, it is also possible for both of them to hold. What I am looking for is an option to encode such an "or" condition on a set of inequalities.

Ofcourse, if we say that $eq{a}_{i}$ is lets say $f(...)\le K$ and $eq{b}_{i}$ is $g(...)\le M$ I can write $f(...)>K+M$, but this demand is too strong, because in my original problem I may allow $g(...)\le M$ (for example) as long as g(...)≤M, but then $f(...)+g(...)>K+M$. So requiring $f(...)+g(...)\le K+M$ is too strong for me.

My question can be divided to 2 questions:

1. Is there any idea for a nice trick here or for some sort of a reduction to Linear Programming?

2. Perhaps there exists a software or an online site which allow this kind of "or"?

I will explain what I mean precisely: Lets say I have a set of inequalities $e{q}_{1}$ to $e{q}_{n}$, which must hold. But, additionally, I have several more inequalities $eq{a}_{1},....,eq{a}_{k}$ and $eq{b}_{1},...,eq{b}_{k}$, that can be partitioned to couples (of the form $\u27e8eq{a}_{i},\phantom{\rule{thinmathspace}{0ex}}eq{b}_{i}\u27e9$ for all $1\le i\le k$), such that either $eq{a}_{i}$ holds or if it doesn't then $eq{b}_{i}$. Nonetheless, it is also possible for both of them to hold. What I am looking for is an option to encode such an "or" condition on a set of inequalities.

Ofcourse, if we say that $eq{a}_{i}$ is lets say $f(...)\le K$ and $eq{b}_{i}$ is $g(...)\le M$ I can write $f(...)>K+M$, but this demand is too strong, because in my original problem I may allow $g(...)\le M$ (for example) as long as g(...)≤M, but then $f(...)+g(...)>K+M$. So requiring $f(...)+g(...)\le K+M$ is too strong for me.

My question can be divided to 2 questions:

1. Is there any idea for a nice trick here or for some sort of a reduction to Linear Programming?

2. Perhaps there exists a software or an online site which allow this kind of "or"?

Answer & Explanation

Freddy Doyle

Expert

2022-07-08Added 20 answers

You can enforce $f\le K\vee g\le M$ by introducing a binary decision variable x and linear "big-M" constraints:

$\begin{array}{}\text{(1)}& f-K& \le {M}_{1}x\text{(2)}& g-M& \le {M}_{2}(1-x)\end{array}$

Here ${M}_{1}$ is a constant upper bound on $f-K$ when $x=1$, and ${M}_{2}$ is a constant upper bound on $g-M$ when $x=0$.

If $x=0$, then constraint $(1)$ forces $f\le K$ and constraint $(2)$ is redundant. If x=1, then constraint $(2)$ forces $g\le M$ and constraint $(1)$ is redundant.

$\begin{array}{}\text{(1)}& f-K& \le {M}_{1}x\text{(2)}& g-M& \le {M}_{2}(1-x)\end{array}$

Here ${M}_{1}$ is a constant upper bound on $f-K$ when $x=1$, and ${M}_{2}$ is a constant upper bound on $g-M$ when $x=0$.

If $x=0$, then constraint $(1)$ forces $f\le K$ and constraint $(2)$ is redundant. If x=1, then constraint $(2)$ forces $g\le M$ and constraint $(1)$ is redundant.

Gauge Terrell

Expert

2022-07-09Added 5 answers

The short answer is no, there is no "nice" way to do it. Geometrically the "or" introduces a union of domains, so what would be a convex polytope with only "and" linear inequalities will instead turn into a union of such things, and probably not convex. The general recourse would be to compare the results of solving separate problems, corresponding to the "or" cases. If you were looking for a maximum value, then you'd take the maximum of results for all the separate subproblems.

Most Popular Questions