Linear programming algorithm that minimizes number of non-zero variables?

You want to find a solution $x$ in your linear system (set of equality and inequality constraints) that has the smallest number of nonzero entries. That would correspond to minimizing the $l_{0}$ norm $\|x\|_{0}$ which is exactly the number of nonzero entries in $x$. Unfortunately, this is not a linear program anymore. In fact it is a very hard problem to solve.

Instead you can "relax" the problem a little bit and solve the following problem \begin{align} \min \quad & \|x\|_{1}\\ \text{subject to:} \quad& \text{your linear constraints} \end{align} Note that $$ \|x\|_{1} = \sum_{i=1}^{n} |x_{i}| $$ and as you can see it intuitively promotes sparsity because every nonzero entry adds to the penalty. More formally, we say that $\|x\|_{1}$ is the convex hull of $\|x\|_{0}$, but don't worry about it now. The bottomline is that you can solve the above problem and hope that you will get a sparse solution.

Note that the above minimization problem is actually a linear program (although you might not be able to say because of the absolute value operation in the $\|x\|_{1}$. If you are using some generic solver like CVX then you can describe directly the objective as minimization of $\|x\|_{1}$ (something like $\text{norm}(x, 1)$). If not, then you can lookup online how the minimization of $l_{1}$ norm corresponds to a linear program.


This problem is studied here:

On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, by Edoardo Amaldi and Viggo Kann, Theoretical Computer Science, December 1998

In short: the smallest number of variables cannot be found in polynomial time, and cannot even be approximated to any constant factor, unless P=NP.