Analysing the effect of candidate selection and instance ordering in a realtime algorithm configuration system

Algorithm configuration has been repeatedly shown to have a large impact on improving the performance of solvers. Realtime algorithm configurators, such as ReACTR, are able to tune a solver online without incurring costly offine training. In order to do this ReACTR adopts a one-pass methodology where each instance in a stream of instances to be solved is considered only as it arrives. As such, the order in which instances are visited can affect the quality of the tuned parameters and, as a result, the solving time. ReACTR uses a selection procedure to choose multiple configurations to run from a set of possible candidates. These configurations are then run in parallel on each instance. A winner, which solves the problem quickest, or achieves the objective value, emerges. The information on this winner is then fed back into a ranking system which is used as part of the selection procedure and the cycle continues for all future instances. This paper explores both the effect of the instance ordering on configuration performance and which candidate selection policy is most effective in each case.