Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed.

Do you know a way to express this constraint in a linear program, in a way that it can be solved using an unmodified simplex implementation ?

For example this constraint : $x_1 \geq 4$ or $x_1 = 0$.

Typical relation between all constraints in a linear program is AND. Here this is an OR between two constraints.

Note : I need to solve problems having multiple variables like this in a computationally efficient way

Thanks

share|improve this question
1  
This can't be done with strict linear programming. If you're willing to employ binary variables and branch and bound, you can do this. –  Michael Grant Jun 27 at 14:53
    
I were hopping I could use a home made linear simplex solver with some tricks :(. –  trinita Jun 27 at 17:25
    
I'm afraid not. It's not linear. There is no way to avoid some sort of branching approach where you decide which "side" of the disjunction to try at each stage. –  Michael Grant Jun 27 at 17:31
    
Thanks. That's bad news. I wish there was some tricks, like the ones used to compute absolute value or min between variables –  trinita Jun 27 at 17:36

2 Answers 2

up vote 2 down vote accepted

Here's the bad news: you can't do this with a straight-up linear program.

Here's the good news: you can do this with an integer linear program.

Introduce an additional binary decision variable $z$. Let $z=0$ whenever $x=0$ and $z=1$ whenever $x\ge 4$. Furthermore, pick an arbitrarily large number, call it $M$, such that $M$ can not bound your $x$ variable too soon(e.g. if your problem data is on the order of $10^2$, pick $M=10^5$ or something). Now add the following constraints to your problem:

$$ x \ge 4z \\ x \le Mz $$

If $z=0$, the constraints force $x=0$. If $z=1$ the constraints force $x \ge 4$ (since $M$ is large enough by definition).

In general, the modeling issue is capturing a situation like this: $$x = 0 \lor x\in[a,b], \quad0<a<b<\infty$$ $x$ is called a semicontinuous variable, and the trick that I've shown you above extends naturally to the following pair of constraints: $$ x \ge az \\ x \le bz $$

Unless you are coding the algorithm yourself, be aware that most commercial solver packages can handle semicontinuous variables internally (by doing the constraint modeling internally and branching on $z$). Read the appropriate documentation for the syntax.

share|improve this answer
    
Thanks for your answer and the term "semicontinuous" that describe my variable. Unfortunately I have a home made implementation of the two-phase simplex and I were hopping I could use it with some tricks :(. –  trinita Jun 27 at 17:24
    
@trinita Nope, you will have to also implement a home-brew version of a branch-and-bound scheme in order to accommodate semi-continuity. Honestly, you're better off examining the source code of some open-source projects such as GLPK or COIN-OR. –  baudolino Jun 27 at 17:43
    
@trinita BTW, welcome to Math.SE. If you like this answer and feel it adequately captures your question, please upvote and accept. –  baudolino Jun 27 at 17:47
    
Ok I will look into branch-and-bound method –  trinita Jun 27 at 17:53

Another possible constraint:

$y_1(x_1-4-z_1)+(1-y_1)\cdot x_1=0$

$y_1 \in \{0,1 \}, z_1 \geq 0$

share|improve this answer
    
This is not linear programming, cause there is a product between variables and also binary variables. –  trinita Jun 27 at 17:29
    
You are right. As baudolina has said already, you can´t mangage the problem with a straight-up linear program. It was only another (simple) suggestion. –  calculus Jun 27 at 17:37
    
Ok thanks for the suggestion –  trinita Jun 27 at 17:45
    
You are welcome. If you are looking for a optimization program try Lingo. The "coding language" is quiet simple. And it is for free for a certain maximum number of variables. –  calculus Jun 27 at 18:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.