Non-sparse solution for a linear programming problem

Question

I have formulated a linear program with equality, inequality and non-negativity constraints. My objective function is the minimization of a linear combination of decision variables (with different coefficients for different variables). I have 7803 decision variables, 51 inequality constraints and 111 equality constraints. I used the simplex method and found the solution. In the solution the values for most decision variables is 0 (like 98%), which is not surprising, based on the model formulation. Because of the nature of the problem, I need to have a way larger ratio of the decision variables with non-zero values in the solution. Is there any formulation technique that can do this for me? In other words, I need to modify my formulation (I guess probably in the OF) to find a less-sparse solution, at the cost of getting a little far from the optimum point. I am okay if it ends up in a non-linear optimization problem.

Answer 1

A simple trick is to solve the LP resulting in the solution $x^{\star}$. As you don't like this solution, you now solve a new LP with the old constraints and additional constraint that $c^Tx = c^Tx^{\star}$ (i.e., just as good) but minimize the distance to what you think is a good solution (such as $\left\| x-1 \right\|_2^2$).

Answer 2

There is an non convex optimisation based approach used in signal processing : you can use NMF with sparse constraints. Use a multiplicative gradient descent with l1 regularisation step, and project your inequality constraint at each step.

EDIT: Roughly the idea of Lee, DD & Seung, HS (1999) is to use a "multiplicative" gradient update to maintain nonegativity during the factorisation : split the gradient into two positive components $g=g_+−g_−g$ and update using $g_+/g_−$ direction.

Then you can include constraint inside the gradient descent, that would be the fuzzy part of my proposal. See & Seung algorithm as very little mathematical guarantees but somehow performs very well. There are a lot of contrained variants of NMF, you can check J. Le Roux, J. R. Hershey, and F. Weninger. "Sparse NMF – half-baked or well done ?" for sparse constraints.

Answer 3

You could just add constraints of the form $x_i \ge \epsilon$ for some of the variables, where $\epsilon$ is the smallest positive value you would allow as "non-zero". You might choose the variables with smallest shadow prices in your optimal solution of the original problem.

Answer 4

It is not surprising that your current solution has so many variables with value zero especially if your solver uses the simplex method instead of an interior point method. When you say "Because of the nature of the problem, ..." it means that your current model does not represent your actual problem (it is not the right model) and you should formulate the problem differently. Anyway, here is what you should consider. Given that your current problem is a linear program we can consider two cases:

1. Your linear program has a unique optimal solution.

2. Your linear program has alternative optimal solutions.

In the first case, it is impossible to increase the Number of Positive Variables (NPV) without making the optimal value worse. So you need to change your problem if you really want to increase the NPV. You need to solve a two-objective optimization problem to maximize NPV while optimizing your original objective function. There are different ways to formulate and solve multi-objective problems. For example, you may consider a convex combination (or weighted average) of the two objective function as your new objective function and solve the problem by typical methods used for single-objective problems.

In the second case, you may find another optimal solution for the problem with a better value of the NPV. To find such a solution, you may define a secondary objective for the problem. The new problem is considered as a lexicographic multi-objective problem which can be solved taking two approaches. The first approach is to define an objective function that maximizes the NPV without influencing the primary objective and then use typical single-objective methods to solve the problem (finding such an objective function is sometimes difficult but may be possible). The second approach is to solve a sequence of single-objective problems (once you solve the original problem, you transmit some information to a second problem whose objective is maximizing the NPV).

As you see, in both cases you need two objective functions. Given the number of variables and constraints of your problem it should be easy to solve even if you add some integer variables to your model. Note that your problem becomes a mixed integer program that may be solved by MILP solvers. I suggest to define binary variable $y_i\in\{0,1\}$ corresponding to each $x_i$ and add the constraints $l_i\, y_i \le x_i \le u_i\,y_i$ for each $i$, where $u_i$ is an upper bound on the variable $x_i$ (or a big-M parameter) and $l_i$ is any positive number as the lower bound of $x_i$ (e.g., $l_i = \epsilon$). Note that such a lower bound is effective only if $y_i=1$ and this is a decision that is made by the optimization problem itself. You can now consider $\max (\sum_{i} y_i)$ or $\min (-\sum_{i} y_i)$ as another objective of the problem. You can formulate the problem as a MILP (not a nonlinear program).

Note that you should still find the right single-objective model of your problem and what I mentioned here may give you some insight to do so.