3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ are you sure you meant: "all possible algorithms", instead of "all possible solutions"? $\endgroup$
    – Suvrit
    Aug 11, 2012 at 14:23

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – ashade
    Aug 11, 2012 at 14:56
  • $\begingroup$ 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. $\endgroup$ Aug 12, 2012 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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