• Gurobi Staff

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

• Gurobi Staff

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

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>)

• Gurobi Staff

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