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

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.

• I am a little confused by the description. Are the $c_{i}$'s given to you or you introduced them to promote sparsity? By sparsity I mean small number of nonzero entries in $x$. Also, the simplex method is just a method to solve general linear programs. I am not sure why we are talking about the method here. The question is what is the right linear program to formulate. In general, the standard approach is to solve something like $\min \|x\|_{1}$, subject to your equality constraints. Vaguely speaking, minimizing the $\|x\|_{1}$ pushes the number of nonzero entries lower. – megas Dec 25 '14 at 4:53
• Yes the $c_i$s are to promote sparsity. At one point I did need the simplex method because I thought I did want to minimize the objective function, but found given the constraints I cared less about the minimum and more about just finding a solution. It probably isn't the right linear program to use anymore, hence the question. – Nathanial Dec 25 '14 at 5:10
• I drafted an answer to your question. I hope it helps. – megas Dec 25 '14 at 5:23
• Penalizing the $L_1$ norm of $x$ in order to promote sparsity is a very popular technique in optimization. – littleO Dec 25 '14 at 5:49

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.

• It's for software I'm writing. It looks like I may be able to use GLPK for $l_1$ norm minimization. Thank you. – Nathanial Dec 25 '14 at 6:34
• good luck! if you are using python, keep in mind that CVXOPT is also a package for python. – megas Dec 25 '14 at 6:44
• So I want the CVXOPT $l_1$ norm approximation, right? cvxopt.org/examples/mlbook/l1.html – Nathanial Jan 14 '15 at 0:53
• I guess... with $P$ set to identity matrix and $q$ set to the $0$ vector. – megas Jan 14 '15 at 3:36
• That's what I'm doing, I just wanted to make sure $l_1$ norm approximation is the same as what we are talking about. Thanks! – Nathanial Jan 14 '15 at 18:22

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.