DistNet: Neural Networks for Predicting Algorithm Runtime Distributions

Many state-of-the-art algorithms for solving hard combinatorial problems in artificial intelligence include elements of stochasticity that lead to high variations in runtime, even for a fixed problem instance. Knowledge about the resulting runtime distributions (RTDs) of algorithms on given problem instances can be exploited in various meta-algorithmic procedures, such as algorithm selection, portfolios, and randomized restarts. We use neural networks to approach this task and demonstrate that the parameters of an RTD should be learned jointly and that neural networks can do this well by directly optimizing the likelihood of an RTD given runtime observations.

K. Eggensperger, M. Lindauer, F. Hutter
Neural Networks for Predicting Algorithm Runtime Distributions
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI’18)

Code accompanying the paper is here.
Data used in the paper can be downloaded here. Results obtained from running the code can be downloaded here.