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 e q a 1 , . . . . , e q a k and e q b 1 , . . . , e q b k , that can be partitioned to couples (of the form ⟨ e q a i , e q b i ⟩ for all 1 ≤ i ≤ k), such that either e q a i holds or if it doesn't then e q 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 e q a i is lets say f ( . . . ) ≤ K and e q b i is g ( . . . ) ≤ M I can write f ( . . . ) &gt; K + M, but this demand is too strong, because in my original problem I may allow g ( . . . ) ≤ M (for example) as long as g(...)≤M, but then f ( . . . ) + g ( . . . ) &gt; K + M. So requiring f ( . . . ) + g ( . . . ) ≤ 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"?

Question

I am looking for a way to express an &quot;or&quot; 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   e  q      a    1    ,  .  .  .  .  ,  e  q      a    k   and   e  q      b    1    ,  .  .  .  ,  e  q      b    k  , that can be partitioned to couples (of the form       ⟨    e    q          a      i        ,        e    q          b      i        ⟩   for all   1  ≤  i  ≤  k), such that either   e  q      a    i   holds or if it doesn&#039;t then   e  q      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 &quot;or&quot; condition on a set of inequalities.Ofcourse, if we say that   e  q      a    i   is lets say   f      (    .    .    .    )    ≤  K and   e  q      b    i   is   g      (    .    .    .    )    ≤  M I can write   f      (    .    .    .    )    &amp;gt;  K  +  M, but this demand is too strong, because in my original problem I may allow   g      (    .    .    .    )    ≤  M (for example) as long as g(...)≤M, but then   f      (    .    .    .    )    +  g      (    .    .    .    )    &amp;gt;  K  +  M. So requiring   f      (    .    .    .    )    +  g      (    .    .    .    )    ≤  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 &quot;or&quot;?

Freddy Doyle · Accepted Answer

You can enforce   f  ≤  K  ∨  g  ≤  M by introducing a binary decision variable x and linear &quot;big-M&quot; constraints:                    (1)                    f        −        K                            ≤                  M          1                x                            (2)                    g        −        M                            ≤                  M          2                (        1        −        x        )            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  ≤  K and constraint   (  2  ) is redundant. If x=1, then constraint   (  2  ) forces   g  ≤  M and constraint   (  1  ) is redundant.

Gauge Terrell · Accepted Answer

The short answer is no, there is no &quot;nice&quot; way to do it. Geometrically the &quot;or&quot; introduces a union of domains, so what would be a convex polytope with only &quot;and&quot; 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 &quot;or&quot; cases. If you were looking for a maximum value, then you&#039;d take the maximum of results for all the separate subproblems.