Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is:


minimize: $w^Tx$
subject to: $Ax=b$, $Cx \le d$ and for each $x\_i$, $x\_i = 0$ OR $x\_i \ge k\_i, k\_i > 0$.


EDIT: it is also known that $w \ge 0$ and $A$ and $C$ are binary matrices. Also, $b \ge 0$ and $d \ge 0$.


I want to enumerate possible algorithms for solving this problem. Thankx for all.



linear programming with OR restrictions
Your additional constraints make the feasible region for your problem nonconvex, and thus it cannot be represented as a linear programming problem.


If you can obtain an upper bound $M\_{i}$ on the maximum value of $x\_{i}$, then there is a standard approach to these problems in which the problem is formulated as a 0-1 mixed integer linear programming problem. 


First, we introduce 0-1 variables $y\_{i}$, and add the constraints 


$x\_{i} \geq k\_{i}y\_{i}$


If $y\_{i}$ takes on a 1 value, then $x\_{i}$ is forced to be greater than or equal to $k\_{i}$. If $y\_{i}$ is 0, then this constraint is vacuous. 


Next, we add the constraints 


$x\_{i} \leq M\_{i}y\_{i}$


If $y\_{i}$ is 0, this forces $x\_{i}=0$. If $y\_{i}=1$, then this constraint does nothing. 


This combination of constraints means that either $x\_{i}=0$ and $y\_{i}=0$ or 
$x\_{i}\geq k\_{i}$ and $y\_{i}=1$. 


There are many approaches to solving the resulting 0-1 mixed integer linear programming including branch and bound methods and cutting plane algorithms. In practice, the most powerful methods (implemented in closed source commercial codes such as IBM's CPLEX as well as a number of open source noncommercial software packages) combine these two general approaches into a "branch and cut" approach. 


It is also possible to directly implement these "semi-continuous variables" within a branch and cut algorithm, and this approach does not require an upper bound $M\_{i}$. This feature is available for example in IBM's CPLEX package. 


