I am looking for a way to express an "or" option in a system of linear inequalities for a linear pro

Aganippe76

Aganippe76

Answered question

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 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 ( . . . ) > 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 ( . . . ) > 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"?

Answer & Explanation

Freddy Doyle

Freddy Doyle

Beginner2022-07-08Added 20 answers

You can enforce f K g M by introducing a binary decision variable x and linear "big-M" 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

Gauge Terrell

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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?