Complexity analysis

Answered

Yali Chen

• June 25, 2024 09:41

For 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

0

• 

  Aron Zingler

  • July 17, 2024 10:37
  • Edited

  

  

  

  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

Please sign in to leave a comment.