Complexity analysis
AnsweredFor the formulated optimization problem, I design an algorithm primarily based on Gurobi solving, which means that I mainly use the Gurobi to solve my optimization problem. In thi case, how to analyze the complexity of the algorithm? Many thanks!
All the best,
Yali
-
Official comment
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
I think you will have to specifiy which kind of optimization problem your are solving with Gurobi.
LP,QP, MILP, QCQP or nonconvex MINLP.Also, you will have to specify if you are interested in worst-case or average-case complexity and in terms of what.
Suppose you are solving an LP; then the worst-case complexities of the simplex and barrier method in terms of input length are well-researched. I think the Gurobi team has made great efforts to reduce what one might call 'real-world-average' complexity; I do not think that they really focused on guarantees for the mathematical worst-case complexity so far.
Maybe giving a complexity in terms of LP solves would be more sensible.
0
Post is closed for comments.
Comments
2 comments