Understanding rigor of Gurobi MIP solver in non-convex setting
AnsweredI am an academic who is trying to use Gurobi to verify that a 48x48 matrix is copositive (ie, for all vectors \(v \in \Bbb{R}_{\ge 0}\), we have that \(v^T M v \ge 0\)). I am using 48 variables, for the 48 entries of \(v\). Since there are no linear terms, we may assume the smallest non-zero variable takes the value one, and it suffices to show that there is some large \(C > 0\) such that \(v^T M v \ge -C\).
When I run my program, the method it says it is using is an MIP solver. (it also said its using roughly 600 continuous variables, which feels sorta off to me, should that be 48?) It has been running for 20 hours now, bouncing between 54000 and 56000 unexplored nodes, and I just wanted to make sure this is the right solver for my purposes.
First off, if the program halts and says my quadratic form does not take any negative values, how certain should I be that this true? I am seeking rigorous confirmation of copositivity, so I do not want to use a method which could plausibly give a false positive (no puns relating to copositive intended). One of my coefficients is \(\sqrt{5}\), should I replace this with a rational approximation to reduce risk of floating point error?
Secondly, how certain should I be that the process will half, given that my parameters are non-convex. Is it usual to be stuck with 54000-56000 for extended period of time?
-
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?. -
-
-
Hi Zach,
When I run my program, the method it says it is using is an MIP solver.
This statement does not mean that Gurobi reformulated your model into a MIP. It means that w.r.t. branching, it treats bilinear variables as if they would be of type integer. This does not mean that your continuous bilinear variables become integer ones. It means that we can now branch on continuous variables in the sense of a spatial B&B algorithm.
it also said its using roughly 600 continuous variables, which feels sorta off to me, should that be 48?
Gurobi introduces additional variables to handle bilinear terms. An auxiliary variable is introduced for each bilinear term, i.e., the term \(\dots + x \cdot y + \dots\) is replaced by \(\dots + z + \dots\) and the equality constraint \( z = x\cdot y\) is introduced. Gurobi may then perform additional presolving to remove and add variables occurring in bilinear terms.
It has been running for 20 hours now, bouncing between 54000 and 56000 unexplored nodes, and I just wanted to make sure this is the right solver for my purposes.
Please note that while Gurobi may be the right solver, it does not make your problem any easier. Proving co-positivity is co-NP-complete making it extremely difficult. For quadratic problems in general, it is strongly recommended to provide tight variable bounds. In your case, this would mean that you should bound the entries of \(v\). Additionally, choosing the right large value for \(C\) may be tricky, because it may have a negative effect on the numerics of the problem. It may be better to introduce \(C\) as a variable with a variable range of \([10^3,10^6]\) to begin with and then check how far you can go.
First off, if the program halts and says my quadratic form does not take any negative values, how certain should I be that this true?
If there are no signs of numerical issues, you can be sure that the solution returned by Gurobi is correct up to the specified computation tolerances.
One of my coefficients is √5, should I replace this with a rational approximation to reduce risk of floating point error?
It depends, cf Avoid rounding of input, and whether an approximation of \(\sqrt{5}\) is good enough for your application.
Secondly, how certain should I be that the process will half, given that my parameters are non-convex. Is it usual to be stuck with 54000-56000 for extended period of time?
Theoretically, your problem is guaranteed to converge at some point in time. Obviously, the theoretical guarantee does not help you much in practice. How large is the MIPGap after 20 hours? Is it lesser or greater than 1 %? It is often the case with quadratic problems that the last bit of convergence, i.e., bringing the gap far \(< 1\%\) is the hardest and might not be necessary, because the optimal solution has already been found and you are waiting for the proof of optimality only (i.e., for the lower bound to converge).
Best regards,
Jaromił0 -
-
Thanks Jaromil! Is it still guaranteed to halt in the non-convex case? I was aware that copositivity is coNP-complete, but I was hoping it was one of such problems where modern methods can efficiently handle the problem (at least given a few days). I am away from my computer right now, but I assume the MIPgap is undefined, since taking v=0...0 gives the (conjectured to be minimal) value of 0, and if we’re to prove any lower bound the matrix would be copositive. Thanks again, Zach.
0 -
-
-
Is it still guaranteed to halt in the non-convex case?
Yes. However, for very hard problems, it is very likely possible that you run out of memory before convergence has been achieved.
I guess, you modeled your problem as a pure feasibility problem. You might want to experiment with the NoRelHeurTime and MIPFocus parameters to find a feasible point.
0 -
Post is closed for comments.
Comments
4 comments