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?