Candidate selection and instance ordering for realtime algorithm configuration

dc.contributor.authorFitzgerald, Tadhg
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.description.abstractMany 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.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.identifier.citationFitzgerald, T. and O'Sullivan, B. (2019) 'Candidate Selection and Instance Ordering for Realtime Algorithm Configuration', Fundamenta Informaticae, 166(2), pp. 141-166. doi: 10.3233/FI-2019-1798en
dc.identifier.journaltitleFundamenta Informaticaeen
dc.publisherIOS Pressen
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 2019 IOS Press All rights reserved.en
dc.subjectConstraint satisfactionen
dc.subjectBoolean satisfiabilityen
dc.subjectAlgorithm configurationen
dc.titleCandidate selection and instance ordering for realtime algorithm configurationen
dc.typeArticle (peer-reviewed)en
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
490.14 KB
Adobe Portable Document Format
Accepted version
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
2.71 KB
Item-specific license agreed upon to submission