Expressing an OR constraint in linear programming

Question

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?

Are you asking about a particular language/framework, or is this just a math question? — Carcigenicate
– Carcigenicate, Commented Jun 22, 2018 at 12:10
It's not about a particular language or framework. If there is a solution to this problem it should be possible to express this constraint in any language/LP framework, shouldn't it? — Bobface
– Bobface, Commented Jun 22, 2018 at 12:12
Apart from the given answer, this is an example of section 7.1: A variable taking discontinuous values in AIMMS Modeling Guide - Integer Programming Tricks. — sascha
– sascha, Commented Jun 22, 2018 at 14:08
This is called a semi-continuous variable. Most MIP solvers can handle this directly. It is also possible to use a binary to model this. . — Erwin Kalvelagen
– Erwin Kalvelagen, Commented Jun 22, 2018 at 17:37

josliber · Accepted Answer · 2018-06-22 14:07:56Z

8

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

answered Jun 22, 2018 at 14:07

josliber

44.4k12 gold badges103 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Expressing an OR constraint in linear programming

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related