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?
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.