Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
are you sure you meant: "all possible algorithms", instead of "all possible solutions"? –  Suvrit Aug 11 '12 at 14:23
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Great answer, but forgive me, I don't have much knowledge in graph theory. Suppose I have a maximum independent set for this graph. What should I do next to solve my problem? Also, how can I find this maximum independent set? Thanks for you time. –  ashade Aug 11 '12 at 14:56
    
My answer was just to demonstrate that the problem is NP-hard, unlike the standard linear programming problem that is polynomial time. This knowledge is not particularly useful in practice except to eliminate possible approaches. –  Brendan McKay Aug 12 '12 at 1:52
    
Ok, fine comment then. thanks! –  ashade Aug 12 '12 at 16:23
add comment

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.