1
$\begingroup$

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?

  • 0
    @Amr It can be assumed the variables are non-negative reals that can be (if needed) bounded.2012-12-08

2 Answers 2

4

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.

1

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.