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.

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero?

I suspect this would already be enough to simulate integer programming with it and hence it is not possible (without an exponential number of constraints).

Can someone confirm my intuition?

share|improve this question
    
the variables are binary ? –  Amr Dec 8 '12 at 12:25
    
@Amr The binaries are reals. Can a linear program actually have binary variables? –  Jernej Dec 8 '12 at 12:31
    
So the variables are real ? –  Amr Dec 8 '12 at 12:32
    
@Amr It can be assumed the variables are non-negative reals that can be (if needed) bounded. –  Jernej Dec 8 '12 at 12:38
add comment

1 Answer

up vote 3 down vote accepted

If the variables are reals this is not possible. Consider the case when $n=2$ and $k=1$. If it is possible to express the constraint "exactly one of them is non nonzero" using inequalities, then we find that the feasible region $S$ is a convex set. Clearly, $(0,1),(1,0)\in S$. Since $S$ is convex, therefore the line segment joining $(0,1),(1,0)$ is a subset of $S$. Hence, $(1/2,1/2)\in S$ (becasue it lies on the line). This is a contradiction because $(1/2,1/2)$ does not satisfy the constraint that exactly one of the variables is non zero.

share|improve this answer
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.