Resumen
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
Catedrático de Universidad
Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.