Exploiting machine learning for combinatorial problem solving and optimisation
dc.check.embargoformat | Not applicable | en |
dc.check.info | No embargo required | en |
dc.check.opt-out | No | en |
dc.check.reason | No embargo required | en |
dc.check.type | No Embargo Required | |
dc.contributor.advisor | O'Sullivan, Barry | en |
dc.contributor.author | Hurley, Barry | |
dc.contributor.funder | Science Foundation Ireland | en |
dc.contributor.funder | Seventh Framework Programme | en |
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.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.description.status | Not peer reviewed | en |
dc.description.version | Accepted Version | |
dc.format.mimetype | application/pdf | en |
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 | https://hdl.handle.net/10468/5374 | |
dc.language.iso | en | en |
dc.publisher | University College Cork | 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 |
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.thesis.opt-out | false | |
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 |
ucc.workflow.supervisor | b.osullivan@cs.ucc.ie |