Empirical Complexity Analysis of Optimization Algorithms

Modern solvers for combinatorial optimization problems are often the result of hybridizing several algorithmic techniques. Algorithmic frameworks such as MORK enable rapid prototyping and automatic design of such solvers. It is, however, difficult to explain the runtime behavior of complex solvers, whose algorithmic complexity may not be easy to analyze theoretically. In this work, we propose an empirical analysis of the runtime behavior of algorithms that provides an explanation of their complexity using big-Theta (Θ) notation. Our method relies on instrumenting algorithmic components and recording their runtimes, fitting the empirical data to various theoretical complexity models, and finally combining those individual models into a full model that matches the runtime data of the complete algorithm. We demonstrate its applicability, first, on a synthetic dataset, and then, on a state-of-the-art algorithm for a combinatorial optimization problem. In both cases, our method correctly predicts how the algorithmic components scale as instances become more challenging to solve.