# Linear programming: expressing the fact that precisely $k$ variables are nonzero

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?

-
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

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.
If your variables have (finite) bounds $$L_i \leq x_i \leq U_i$$ then you can introduce binary variables $$z_i \in \{0,1\}$$ and linear constraints $$z_i L_i \leq x_i \leq z_i U_i$$ so $$z_i = 0 \implies x_i = 0$$ The constraint $$\sum z_i = k$$ means that at most k of them are non-zero.