LP-presolve and MIP-Presolve for relaxed cardinality problems
Hello,
and first of all thanks for the great software!
I am currently trying to solve cardinality minimization problems, which can thus be written
as Mixed Integer Linear Programs.
However, I want to explore how well I can do by considering instead the convex relaxation of this problem,
as an l1-norm minimization.
(see here for an example the lecture from Stephen Boyd http://cpc.cx/rN7 ).
What I notice is that in many cases where the l1-norm relaxation fails to converge to the optimum cardinality, whether the variable should be a 0 or a 1 could easily be decided using the MIP-presolve function provided with gurobi.
Therefore, I would like to study the possibility of doing something like this:
a) Write the MIP problem and presolve it
b) Use the resulting model to write a new, relaxed l1-norm minimization problem with the additional constraints and hopefully obtain convergence.
I thus have two questions:
1) Do you think this is stupid ?
2) If this somehow makes sense, I am not sure how to convert the presolved MIP model into a l1 model and would appreciate some pointers to make an efficient conversion ! (This question is not about how to relax an MIP problem, but more a programming question in terms of how can I efficiently create my relaxed model from the presolved MIP model).
Thanks a lot for your insight !
Sincerely
Steve
-
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?. -
Post is closed for comments.
Comments
1 comment