# 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. Dec 25, 2014 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. Dec 25, 2014 at 5:10
• I drafted an answer to your question. I hope it helps. Dec 25, 2014 at 5:23
• Penalizing the $L_1$ norm of $x$ in order to promote sparsity is a very popular technique in optimization. Dec 25, 2014 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. Dec 25, 2014 at 6:34
• good luck! if you are using python, keep in mind that CVXOPT is also a package for python. Dec 25, 2014 at 6:44
• So I want the CVXOPT $l_1$ norm approximation, right? cvxopt.org/examples/mlbook/l1.html Jan 14, 2015 at 0:53
• I guess... with $P$ set to identity matrix and $q$ set to the $0$ vector. Jan 14, 2015 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! Jan 14, 2015 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.

Your variables are x[1..n]. Generate a corresponding set of binary variables b[1..n].

The constraint on each b[y] is as follows:

b[y] * bigM >= x[y]

Big M is a constant that is will always be larger than any value of x.

Your optimisation is now to minimise the sum of the b array.

Note: this is now "integer programming", not "linear programming", and so optimal solutions will take longer to find. You might be able to avoid this if you can reconstruct the problem so that x itself will either be a constant value or zero. Another alternative that might work in some scenarios is to run the linear version of the model multiple times with various combinations of variables missing (or constrained to zero) just to see whether that particular set of variables alone can make a feasible solution.