Worst-case complexity non-convex model
Answered
Hi,
I’m solving a non-convex quadratic problem with Gurobi and I was wondering what the worst-case complexity is. Is it exponential (i.e. O(2^n))?
Thank you!
-
Hi Nan,
The worst-case complexity to solve a non-convex (mixed-integer) continuous model using the spatial Branch-and-Bound algorithm is exponential. You can see that by the fact that in worst case, you not only have to branch once on every variable but in worst case you have to branch multiple times on every continuous variable. In worst, you have to branch on every variable until some \(\epsilon\) termination criterion is reached. I am not aware of a fixed formula in big \(\mathcal{O}\) notation but it is definitely exponential.
For more details on the finiteness proof of spatial B&B algorithm, you might want to have a look at Horst & Tuy (1996) Global Optimization.
Best regards,
Jaromił0 -
Hi Jaromil, thank you for the explanation! I indeed see in the log that the model is solved as a MIP (Continuous model is non-convex — solving as a MIP). However, when I was solving different models, I noticed that some models have extra output lines like ‘Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model).’ I searched in the Gurobi documentation and I think that this is because of the Method parameter (which I haven’t specified, so must have the default value of -1 I guess). Just to be sure: the worst-case complexity of all these methods is still exponential, right?
0 -
Hi Nan,
The line about "Deterministic concurrent LP optimizer" you see is about solving the root relaxation which is usually an LP. As you already correctly noted, this is defined by the Method parameter. (non)convex MI(N)LPs solve many LPs during the solution process.
As long as you are not solving a continuous LP, the complexity is exponential.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments