Optimal LP solution with minimum number of non-zero variables
AnsweredI have an LP problem with a pretty standard formulation:
\[ \begin{align} &\min d^T p \\ \text{s.t. } &Ap \leq b \\ &\sum_i p_i = 1 \\ &p \geq 0 \end{align} \]
(The vector \(p\) is a vector of probabilities so I decided to add this constraint here explicitly if that is of any importance.)
I want to find the optimal solution with an additional requirement that the number of non-zero entries in \(p\) is minimal (among all the optimal solutions). I think this might be formulated with multiple objectives but I don't really understand how.
P.S. The number of variables is a couple of thousands.
P.P.S. If finding such an optimal solution is very hard, perhaps, some good heuristic method would work for me too. In other words, I want an optimal solution with fewer non-zero variables.
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
I want to find the optimal solution with an additional requirement that the number of non-zero entries in p is minimal (among all the optimal solutions). I think this might be formulated with multiple objectives but I don't really understand how.
Your problem is an LP. Does your statement mean that you know that there is an infinite number of optimal solutions to your problem and you are looking for the one with the most zeros in the solution point?
In this case you might want to have a look at the Knowledge Base article How do I find additional solutions to a model? This would lead to your idea of introducing a heuristic to find solutions with fewer nonzeros.
An alternative would be to introduce binary variables to track whether a variable is \(0\) or not. You could use indicator constraints
\[b_i=1 \rightarrow p_i\leq 0\]
which state that if variable \(b_i=1\), then \(p_i\) equals \(0\). You would then have to add these binary to your objective function with negative coefficients to reward the case that \(b_i=1\). Note that this would make your LP a MIP and will very likely result in some performance loss. Since you said, that the number of your variables is "only" a few thousand, this is definitely worth a try.
Best regards,
Jaromił1 -
-
Thanks, Jaromił.
(Sorry, I thought I posted my reply on Friday but now I see that I actually didn't.)Your problem is an LP. Does your statement mean that you know that there is an infinite number of optimal solutions to your problem and you are looking for the one with the most zeros in the solution point?
I don't know how many optimal solutions my problem has. If it's unique then the problem is trivial (this optimal solution is also the optimal solution with the most zeroes). But of course, I care more about the case when the number of optimal solutions is infinite.
I think the links you provided are exactly what I need and I am looking into it.
Cheers,
Yauhen0 -
Post is closed for comments.
Comments
3 comments