Abstract
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.
J. Manuel Colmenar
Full Professor
My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.