TY - GEN
T1 - Learning a stopping criterion for local search
AU - Arbelaez, Alejandro
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - Local 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.
AB - Local 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.
UR - https://www.scopus.com/pages/publications/85006880785
U2 - 10.1007/978-3-319-50349-3_1
DO - 10.1007/978-3-319-50349-3_1
M3 - Conference proceeding
AN - SCOPUS:85006880785
SN - 9783319503486
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 16
BT - Learning and Intelligent Optimization - 10th International Conference, LION 10, Revised Selected Papers
A2 - Festa, Paola
A2 - Sellmann, Meinolf
A2 - Vanschoren, Joaquin
PB - Springer Verlag
T2 - 10th International Conference on Learning and Intelligent Optimization, LION 10
Y2 - 29 May 2016 through 1 June 2016
ER -