Lazy constraints not working?
I'm solving a mixed-integer semidefinite programming (SDP) problem using lazy constraints in the callback for the SDP constraint. That is, when Gurobi found a feasible solution, I add a lazy constraint that cut off the solution if the matrix composed this feasible solution is not positive semidefinite (PSD). However, when I check the optimal solution, the matrix composed is not PSD. It seems that lazy constraints are not active.
-
Official comment
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?. -
That is an interesting approach. I actually did something very similar for my PhD thesis a couple of years ago. Just out of curiosity, how are you calculating the lazy constraints, what routines are you using and how are you dealing with numerical issues.
From what you describe it is possible that you have numerical issues or that the lazy constraints are not added everywhere they need to be added. Please be aware that you have to add the lazy constraints every time they are violated. This can mean that you have to add them more than once.
Here is the corresponding link to our documentation. And this is the important part: "Your callback should be prepared to cut off solutions that violate any of your lazy constraints, including those that have already been added. Node solutions will usually respect previously added lazy constraints, but not always."
Are you sure that you add them every time they are violated?
Best,
Sonja
0 -
Sonja, thank you for your suggestion.
I used "callback" to add lazy constraints. I check, in my callback function, whether the incumbent solution satisfies the SDP constraint. If not, then a lazy constraint is added. So, I can't see where else I should add them.
Now, my lazy constraints work. The output solution is SDP, even if the original mixed-integer SDP problem should be infeasible.
0 -
In what kind of callback are you adding them? So what is the "WHERE" value?
Your last sentence really points to numerical issues. That is not so uncommon when solving SDPs. How do your lazy constraints look like? Also can you share a log file?
Best,
Sonja
0 -
Dear Sonja,
I set WHERE = GRB.Callback.MIPSOL.
I check whether the current incumbent solution gives an SDP constraint by checking the minimal eigenvalue of the solution matrix "X". If the minimal eigenvalue is less than zero, I use the corresponding eigenvector "v" to construct a linear inequality v' * X * v >= 0, and add it to the lazy constraint by "m.cbLazy( ..... )" (Line 2067 in my Python file. Here is the link for the file: <https://www.dropbox.com/s/sx5ztb2gzut6xpd/MSS-SDP-approximation-20200329-v1.py?dl=0>)
0 -
A few remarks/questions:
- How "negative" is the eigenvalue that is not cut off? Numerical issues happen quite frequently when it comes to SDPs.
- Also, how are you computing it? From your code, it seems you are doing this yourself. Please be aware that this is quite expensive and I am a bit worried about the performance of this code.
- Can you share a Gurobi log file?
- How do the lazy constraints look like? Have you tried printing a few and looked at them, if everything is correct there?
- Can you try to also use the WHERE==GRB.Callback.MIPNODE callback to add the lazy constraints?
Best,
Sonja
0
Post is closed for comments.
Comments
6 comments