Learning a stopping criterion for local search

Simple item page
dc.contributor.authorArbelaez, Alejandroen
dc.contributor.authorO’Sullivan, Barryen
dc.contributor.editorFesta, Paolaen
dc.contributor.editorSellmann, Meinolfen
dc.contributor.editorVanschoren, Joaquinen
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderSeventh Framework Programmeen
dc.date.accessioned2024-02-06T14:43:26Z
dc.date.available2024-02-06T14:43:26Z
dc.date.issued2016-12-01en
dc.description.abstractLocal search is a very effective technique to tackle combinatorial problems in multiple areas ranging from telecommunications to transportations, and VLSI circuit design. A local search algorithm typically explores the space of solutions until a given stopping criterion is met. Ideally, the algorithm is executed until a target solution is reached (e.g., optimal or near-optimal). However, in many real-world problems such a target is unknown. In this work, our objective is to study the application of machine learning techniques to carefully craft a stopping criterion. More precisely, we exploit instance features to predict the expected quality of the solution for a given algorithm to solve a given problem instance, we then run the local search algorithm until the expected quality is reached. Our experiments indicate that the suggested method is able to reduce the average runtime up to 80% for real-world instances and up to 97% for randomly generated instances with a minor impact in the quality of the solutions.en
dc.description.sponsorshipScience Foundation Ireland (Grant No. 10/CE/I1853)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationArbelaez, A. and O’Sullivan, B. (2016) 'Learning a stopping criterion for local search', in Festa, P., Sellmann, M. and Vanschoren, J. (eds.) Learning and Intelligent Optimization. LION 2016, pp. 3-16. Lecture Notes in Computer Science, 10079. Springer, Cham. https://doi.org/10.1007/978-3-319-50349-3_1en
dc.identifier.doi10.1007/978-3-319-50349-3_1en
dc.identifier.endpage16en
dc.identifier.isbn9783319503486en
dc.identifier.isbn9783319503493en
dc.identifier.issn0302-9743en
dc.identifier.issn1611-3349en
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage3en
dc.identifier.urihttps://hdl.handle.net/10468/15498
dc.identifier.volume10079en
dc.language.isoenen
dc.publisherSpringer Nature Ltd.en
dc.relation.ispartofLecture Notes in Computer Scienceen
dc.relation.ispartofInternational Conference on Learning and Intelligent Optimization (LION 2016)en
dc.relation.projectinfo:eu-repo/grantAgreement/EC/FP7::SP1::ICT/318137/EU/The DIStributed Core for unlimited bandwidth supply for all Users and Services/DISCUSen
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© 2016, Springer International Publishing Switzerland. This version of the paper has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-319-50349-3_1en
dc.subjectLocal searchen
dc.subjectProblem instanceen
dc.subjectTravel salesman problemen
dc.subjectLocal search algorithmen
dc.subjectAverage runtimeen
dc.titleLearning a stopping criterion for local searchen
dc.typeBook chapteren
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
lion_2016b.pdf
Size:
702.17 KB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Insight Centre for Data Analytics - Conference Items