Aganippe76

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 $⟨eq{a}_{i},\phantom{\rule{thinmathspace}{0ex}}eq{b}_{i}⟩$ 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\left(...\right)\le K$ and $eq{b}_{i}$ is $g\left(...\right)\le M$ I can write $f\left(...\right)>K+M$, but this demand is too strong, because in my original problem I may allow $g\left(...\right)\le M$ (for example) as long as g(...)≤M, but then $f\left(...\right)+g\left(...\right)>K+M$. So requiring $f\left(...\right)+g\left(...\right)\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"?

Freddy Doyle

Expert

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}\left(1-x\right)\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 $\left(1\right)$ forces $f\le K$ and constraint $\left(2\right)$ is redundant. If x=1, then constraint $\left(2\right)$ forces $g\le M$ and constraint $\left(1\right)$ is redundant.

Gauge Terrell

Expert