I have real world problems I'm trying to programmatically solve in the form of
$$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$
Subject to
\begin{align}
& a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} = b_1 \\[6pt]
& 0 \le a_{12} x_1 \le b_2 \\[6pt]
& 0 \le a_{23} x_2 \le b_3 \\
& {}\qquad\vdots \\
& 0 \le a_{nm} x_n \le b_m
\end{align}
Right now I'm using the simplex method. Because of the first constraint there are many solutions and I don't really care to min/max to any particular coefficients. What I really care about is to have as few non-zero variables in the objective function as possible.
A good way to look at it is, I have packages to deliver and $x$s are trucks. I don't care how long they take, I just want to use as few trucks as possible.
One strategy I came up with was to minimize $Z$ and set the objective coefficients to something like:
$$c_n = 10n$$
so that:
$$Z = 10 x_1 + 20 x_2 + \cdots + 10 n x_n$$
This mostly works but is a little hacky and, depending on what $a_{nm}$ is, at times inconsistent.
I'm not married to the simplex method, but it's fast and gives me a solution so I'm using it.
Best Answer
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.