Exploiting machine learning for combinatorial problem solving and optimisation

dc.check.embargoformatNot applicableen
dc.check.infoNo embargo requireden
dc.check.opt-outNoen
dc.check.reasonNo embargo requireden
dc.check.typeNo Embargo Required
dc.contributor.advisorO'Sullivan, Barryen
dc.contributor.authorHurley, Barry
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderSeventh Framework Programmeen
dc.date.accessioned2018-02-06T12:46:36Z
dc.date.available2018-02-06T12:46:36Z
dc.date.issued2016
dc.date.submitted2016
dc.description.abstractThis 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.statusNot peer revieweden
dc.description.versionAccepted Version
dc.format.mimetypeapplication/pdfen
dc.identifier.citationHurley, B. 2016. Exploiting machine learning for combinatorial problem solving and optimisation. PhD Thesis, University College Cork.en
dc.identifier.endpage153en
dc.identifier.urihttps://hdl.handle.net/10468/5374
dc.language.isoenen
dc.publisherUniversity College Corken
dc.relation.projectinfo: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.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.projectinfo:eu-repo/grantAgreement/EC/FP7::SP1::ICT/284715/EU/Inductive Constraint Programming/ICONen
dc.rights© 2016, Barry Hurley.en
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/en
dc.subjectConstraint programmingen
dc.subjectCombinatorial optimisationen
dc.subjectMachine learningen
dc.subjectArtificial intelligenceen
dc.subjectSolver portfolioen
dc.subjectEncodingen
dc.thesis.opt-outfalse
dc.titleExploiting machine learning for combinatorial problem solving and optimisationen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD (Science)en
ucc.workflow.supervisorb.osullivan@cs.ucc.ie
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
thesis-20170116.pdf
Size:
1.95 MB
Format:
Adobe Portable Document Format
Description:
Full Text E-thesis
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
5.62 KB
Format:
Item-specific license agreed upon to submission
Description: