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.
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.
This is so similar to 0-1 programming that it isn't a surprise it is NP-hard. Take a graph, make a variable $x_v$for each vertex $v$, interpret $v$ as "selected" if $x_v=0$ and "not-selected if $x_v\ge 1$. Forbid any other values for $x_v$ (corresponding to $k_i=1$ for each $i$). For each edge $vw$ have constraint $x_v+x_w \le 1$. Minimize $\sum_v x_v$. The selected vertices in the solution is a maximum independent set.
