Candidate selection and instance ordering for realtime algorithm configuration

The submission of new items to CORA is currently unavailable due to a repository upgrade. For further information, please contact Thank you for your understanding.

Show simple item record Fitzgerald, Tadhg O'Sullivan, Barry 2019-07-04T14:58:00Z 2019-07-04T14:58:00Z 2019-03-14
dc.identifier.citation Fitzgerald, 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-1798 en
dc.identifier.volume 166 en
dc.identifier.issued 2 en
dc.identifier.startpage 141 en
dc.identifier.endpage 166 en
dc.identifier.issn 0169-2968
dc.identifier.doi 10.3233/FI-2019-1798 en
dc.description.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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher IOS Press en
dc.rights © 2019 IOS Press All rights reserved. en
dc.subject Constraint satisfaction en
dc.subject Boolean satisfiability en
dc.subject Algorithm configuration en
dc.title Candidate selection and instance ordering for realtime algorithm configuration en
dc.type Article (peer-reviewed) en
dc.internal.authorcontactother Tadhg Fitzgerald, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2019-07-04T14:52:04Z
dc.description.version Accepted Version en
dc.internal.rssid 480536967
dc.internal.wokid WOS:000462084300004
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Fundamenta Informaticae en
dc.internal.copyrightchecked No
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress en
dc.internal.IRISemailaddress en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en

Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement