Analysing the Effect of Candidate Selection and Instance Ordering in a Realtime Algorithm Configuration System
Refereed Conference Meeting Proceeding
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 offline 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.
The 32nd ACM SIGAPP Symposium On Applied Computing
Proceedings of the Symposium on Applied Computing, 2017
Digital Object Identifer (DOI):
National University of Ireland, Cork (UCC)
Open access repository: