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

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 worstcase or averagecase complexity and in terms of what.
Suppose you are solving an LP; then the worstcase complexities of the simplex and barrier method in terms of input length are wellresearched. I think the Gurobi team has made great efforts to reduce what one might call 'realworldaverage' complexity; I do not think that they really focused on guarantees for the mathematical worstcase complexity so far.
Maybe giving a complexity in terms of LP solves would be more sensible.
0
Please sign in to leave a comment.
Comments
1 comment