Ordered racing protocols for automatically configuring algorithms for scaling performance

Automated algorithm configuration has been proven to be an effective approach for achieving improved performance of solvers for many computationally hard problems. We consider the challenging situation where the kind of prob-lem instances for which we desire optimised performance is too difficult to be used during the configuration process. Here, we propose a novel combination of racing techniques with existing algorithm configurators to meet this challenge. We demonstrate that, applied to state-of-the-art solver for propositional satisfiability, mixed integer programming and travelling salesman problems, the resulting algorithm con-figuration protocol achieves better results than previous ap-proaches and in many cases closely matches the bound on performance obtained using an oracle selector. We also re-port results indicating that the performance of our new rac-ing protocols is quite robust to variations in the confidence level of the test used for eliminating weak configurations, and that performance benefits from presenting instances or-dered according to increasing difficulty during the race – something not done in standard racing procedures. Categories and Subject Descriptors [Theory of computation]: Design and analysis of algo-rithm