How to write a constraint of x == 0 or x >= m (a positive constant)?


#1

Dear all,

I want to add a constaint to my problem with the following form:

x = 0 or x >= m, where m is a positive constant.

How should I write this constraint?


(Mark L. Stone) #2

Hi. This is simple to do using a Big M approach for disjunctive constraints (I’ll make my big M, “U”, rather than M to avoid confusion with your m). It requires use of CVX"s MIDCP capability.

We need to have an upper bound on x, I will call it U. Make U the smallest upper bound that you can. So your desired constraints are:
x == 0 or m <=x <= U.
Declare binary variables y1 and y2. Now add constraints
x >= 0
y1 + y2 <= 1
x <= Uy1
x >= m
(1-y2)

Why does this work? y1 + y2 <= 1 implies y1 and y2 can not both be 1.
If y1 =y 2 = 0, then x <= 0 and x >= m, which is impossible (infeasible).
Therefore, either y1 = 0 and y2 =1, or y1 = 1 and y2 = 0.

The case y1 = 0 and y2 = 1 implies x <= 0 and x >= 0, which therefore implies x == 0.
The case y1 = 1, y2 = 0 implies x <= U and x >= m, i.e. m <= x <= U.
Therefore, this should do exactly what you want.


#3

Thank you so much for such a quick reply.

It works.
But I have another question. There are two binary variables here. Can I use just one? And what’s the difference?

Suppose y is a binary variable. Add constraints
x >= 0
x <= Uy
x >= m
y

In the case y = 0, x <= 0 and x >= 0. It gives out x == 0.
In the case y = 1, x >= 0, x <= U and x >= m, which gives out m <= x <= U.


(Mark L. Stone) #4

Yes, of course you are correct, because in my formulation, the only feasible solutions have y2 = 1-y1.

So you passed the “test” (I can say that now, ha ha, but in my defense, it was late at night and I was tired). But you missed the other area for improvement. namely, the constraint x >= 0 is not needed, i.e., is redundant. However, all these formulations are correct, and I doubt it makes much, if any, difference computationally which are used. The mixed integer solver will figure out these redundancies.


#5

Thank you so much for your help. ~