CODEWITHSUNDEEP
constraintslinear-programming
Bobface
Bobface

Reputation: 2952

Expressing an OR constraint in linear programming

I have a floating-point variable x in a linear program which shall be either 0 or between two constants CONSTANT_A and CONSTANT_B:

LP.addConstraint(x == 0 OR CONSTANT_A <= x <= CONSTANT_B)

Of course there is no such thing as an explicit OR in linear programming. Is there a way to express this constraint?

Upvotes: 3

Views: 5273

Answers (1)

josliber
josliber

Reputation: 44309

So let's assume you want the constraint:

x == 0 OR 1 <= x <= 2

It is clear that the feasible region of your linear program is not convex, since x=0 and x=1 are both feasible, but no proper convex combination is feasible. As a result, it is provably impossible to model this with a linear program.

That being said, it is easy to model this if you introduce a binary decision variable y, which takes value 1 if we are in the range and 0 if we are fixed to 0. Then you can model the following:

y <= x <= 2*y
y binary

or, in your fully general case:

y*CONSTANT_A <= x <= y*CONSTANT_B
y binary

Upvotes: 8

Related Questions