Exploiting machine learning for combinatorial problem solving and optimisation

Show simple item record

dc.contributor.advisor O'Sullivan, Barry en
dc.contributor.author Hurley, Barry
dc.date.accessioned 2018-02-06T12:46:36Z
dc.date.available 2018-02-06T12:46:36Z
dc.date.issued 2016
dc.date.submitted 2016
dc.identifier.citation Hurley, B. 2016. Exploiting machine learning for combinatorial problem solving and optimisation. PhD Thesis, University College Cork. en
dc.identifier.endpage 153 en
dc.identifier.uri http://hdl.handle.net/10468/5374
dc.description.abstract This dissertation presents a number of contributions to the field of solver portfolios, in particular for combinatorial search problems. We propose a novel hierarchical portfolio which does not rely on a single problem representation, but may transform the problem to an alternate representation using a portfolio of encodings, additionally a portfolio of solvers is employed for each of the representations. We extend this multi-representation portfolio for discrete optimisation tasks in the graphical models domain, realising a portfolio which won the UAI 2014 Inference Competition. We identify a fundamental flaw in empirical evaluations of many portfolio and runtime prediction methods. The fact that solvers exhibit a runtime distribution has not been considered in the setting of runtime prediction, solver portfolios, or automated configuration systems, to date these methods have taken a single sample as ground-truth. We demonstrated through a large empirical analysis that the outcome of empirical competitions can vary and provide statistical bounds on such variations. Finally, we consider an elastic solver which capitalises on the runtime distribution of a solver by launching searches in parallel, potentially on thousands of machines. We analyse the impact of the number of cores on not only solution time but also on energy consumption, the challenge being to find a optimal balance between the two. We highlight that although solution time always drops as the number of machines increases, the relation between the number of machines and energy consumption is more complicated. We also develop a prediction model, demonstrating that such insights can be exploited to achieve faster solutions times in a more energy efficient manner. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher University College Cork en
dc.rights © 2016, Barry Hurley. en
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/ en
dc.subject Constraint programming en
dc.subject Combinatorial optimisation en
dc.subject Machine learning en
dc.subject Artificial intelligence en
dc.subject Solver portfolio en
dc.subject Encoding en
dc.title Exploiting machine learning for combinatorial problem solving and optimisation en
dc.type Doctoral thesis en
dc.type.qualificationlevel Doctoral en
dc.type.qualificationname PhD (Science) en
dc.internal.availability Full text available en
dc.check.info No embargo required en
dc.description.version Accepted Version
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder Seventh Framework Programme en
dc.description.status Not peer reviewed en
dc.internal.school Computer Science en
dc.check.type No Embargo Required
dc.check.reason No embargo required en
dc.check.opt-out No en
dc.thesis.opt-out false
dc.check.embargoformat Not applicable en
ucc.workflow.supervisor b.osullivan@cs.ucc.ie
dc.internal.conferring Spring 2017 en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/10/IN.1/I3032/IE/New Paradigms in Constraint Programming: Applications in Data Centres/ 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
dc.relation.project info:eu-repo/grantAgreement/EC/FP7::SP1::ICT/284715/EU/Inductive Constraint Programming/ICON en


Files in this item

This item appears in the following Collection(s)

Show simple item record

© 2016, Barry Hurley. Except where otherwise noted, this item's license is described as © 2016, Barry Hurley.
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