Candidate Selection and Instance Ordering for Realtime Algorithm Configuration^*

Article type: Research Article

Authors: Fitzgerald, Tadhg^{; †} | O’Sullivan, Barry

Affiliations: Insight Centre for Data Analytics, Department of Computer Science, University College Cork, Cork, Ireland. tadhg.fitzgerald@insight-centre.org, barry.osullivan@insight-centre.org

Correspondence: [†] Address for correspondence: Insight Centre for Data Analytics, Department of Computer Science, University College Cork, Western Road, Cork, Ireland

Note: [*] This paper is an extended version of work published in the Proceedings of the ACM Symposium on Applied Computing 2017

Abstract: Many modern combinatorial solvers have a variety of parameters through which a user can customise their behaviour. Algorithm configuration is the process of selecting good values for these parameters in order to improve performance. Time and again algorithm configuration has been shown to significantly improve the performance of many algorithms for solving challenging computational problems. Automated systems for tuning parameters regularly out-perform human experts, sometimes but orders of magnitude. Online algorithm configurators, such as ReACTR, are able to tune a solver online without incurring costly offline training. As such ReACTR’s main focus is on runtime minimisation while solving combinatorial problems. 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 ReACTR’s performance is sensitive to the order in which instances arrive. It is still not understood which instance orderings positively or negatively effect the performance of ReACTR. This paper investigates the effect of instance ordering and grouping by empirically evaluating different instance orderings based on difficulty and feature values. Though the end use is generally unable to control the order in which instances arrive it is important to understand which orderings impact Re- ACTR’s performance and to what extent. This study also has practical benefit as such orderings can occur organically. For example as business grows the problems it may encounter, such as routing or scheduling, often grow in size and difficulty. ReACTR’s performance also depends strongly configuration selection procedure used. This component controls which configurations are selected to run in parallel from the internal configuration pool. This paper evaluates various ranking mechanisms and different ways of combining them to better understand how the candidate selection procedure affects realtime algorithm configuration. We show that certain selection procedures are superior to others and that the order which instances arrive in determines which selection procedure performs best. We find that both instance order and grouping can significantly affect the overall solving time of the online automatic algorithm configurator ReACTR. One of the more surprising discoveries is that having groupings of similar instances can actually negatively impact on the overall performance of the configurator. In particular we show that orderings based on nearly any instance feature values can lead to significant reductions in total runtime over random instance orderings. In addition, certain candidate selection procedures are more suited to certain orderings than others and selecting the correct one can show a marked improvement in solving times.

Keywords: Constraint Satisfaction, Boolean Satisfiability, Algorithm Configuration

DOI: 10.3233/FI-2019-1798

Journal: Fundamenta Informaticae, vol. 166, no. 2, pp. 141-166, 2019