Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


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.