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

Question

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.

Answer 1

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.

Answer 2

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.