1
$\begingroup$

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 $eq_1$ to $eq_n$, which must hold. But, additionally, I have several more inequalities $eqa_1,....,eqa_k$ and $eqb_1,...,eqb_k$, that can be partitioned to couples (of the form $\left< eqa_i ,\, eqb_i\right>$ for all $1\leq i \leq k$), such that either $eqa_i$ holds or if it doesn't then $eqb_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 $eqa_i$ is lets say $f\left(...\right) \leq K$ and $eqb_i$ is $g\left(...\right) \leq M$ I can write $f\left(...\right)+g\left(...\right) \leq K+M$, but this demand is too strong, because in my original problem I may allow $f\left(...\right) > K+M$ (for example) as long as $g\left(...\right) \leq M$, but then $f\left(...\right)+g\left(...\right) > K+M$. So requiring $f\left(...\right)+g\left(...\right) \leq 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? (A reduction from an instance in which you have couples of inequalities with an or, to a regular instance of LP)
  2. Perhaps there exists a software or an online site which allow this kind of "or"? I am using this site: https://online-optimizer.appspot.com/. However, if there are other sites or software which have such a built in option for an "or", it'd be great as well.

If my inequalities are too generic, I know that most of them seem from the form $x_{i_1}+x_{i_2}+x_{i_3} \leq K$, where $K$ is the same $K$ for all the inequalities, and the rest are either $x_{i_1}+x_{i_2} \leq K$ or $x_{i_1}+x_{i_2}+x_{i_3}+x_{i_4} \leq K$.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ The solution set of a system of linear inequalities is convex, but the solution set of a system involving ‘or’ usually will not be. $\endgroup$
    – LSpice
    Commented Jan 5, 2021 at 22:06
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/3974002/… $\endgroup$
    – RobPratt
    Commented Jan 5, 2021 at 22:09
  • 1
    $\begingroup$ If you think of your inequalities as just being statements, then arbitrary ANDs and ORs of those can be reduced to disjunctive normal form (an OR of AND expressions). These AND expressions are linear programs sovable by Fourier-Moskowitz etc, and correspond (as @LSpice mentioned) convex bodies. The problem is that there may be many of them, you can get an "exponential explosion" in the number of sub-programs. $\endgroup$
    – J.J. Green
    Commented Jan 5, 2021 at 22:12
  • $\begingroup$ @J.J.Green This is an interesting approach. Just to make sure, my problem can be written as a conjunctive normal form (AND among all the equations-couples, and in each couple an OR statement), and by writing it as a disjunctive normal form, I get multiple sets of equations, and each solution will fit to my problem, so I will take the minimal (assuming I want to min in my LP) one, yes? Also, I have searched for "Fourier-Moskowitz", but found no results. Is this a software? $\endgroup$
    – Eric_
    Commented Jan 5, 2021 at 22:21
  • 1
    $\begingroup$ The disjunctive normal form approach will almost certainly be much slower than solving the mixed integer linear programming formulation in my linked answer. $\endgroup$
    – RobPratt
    Commented Jan 6, 2021 at 1:43

1 Answer 1

Reset to default
1
$\begingroup$

In Integer Linear Programming, the disjunction of linear inequalities $f\left(...\right) \leq K$ and $g\left(...\right) \leq M$ can be encoded by introducing two binary variables $p,q\in\{0,1\}$ and three inequalities: \begin{split} f\left(...\right) &\leq K + Cp,\\ g\left(...\right) &\leq M +Cq,\\ p+q & \leq 1, \end{split} where $C$ is a large positive constant. The idea is that the large value of $C$ when it comes with a nonzero coefficient silences the corresponding inequality (making it automatically satisfied).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Or you can omit the $p+q \le 1$ constraint and use only one binary variable, as in my linked answer. $\endgroup$
    – RobPratt
    Commented Jan 6, 2021 at 16:48
  • $\begingroup$ Yes, but having $p,q$ allows fine control over which inequalities are satisfied and which are not. E.g., this can be used if one wants to maximize the number of satisfied inequalities. $\endgroup$
    – Max Alekseyev
    Commented Jan 6, 2021 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .