Lazy constraints not working?
I'm solving a mixedinteger 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.

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

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 mixedinteger SDP problem should be infeasible.

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/MSSSDPapproximation20200329v1.py?dl=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
Please sign in to leave a comment.
Comments
5 comments