EasyLocal++ a 25-year Perspective on Local Search Frameworks: The Evolution of a Tool for the Design of Local Search Algorithm
Pages 1658 - 1667
Abstract
EasyLocal++ is a white-box C++ framework for designing local search algorithms. Over the years, it has been successfully used across various domains, such as timetabling, rostering, scheduling, and logistics, and has produced state-of-the-art results in benchmark datasets and competitions. Beyond research, EasyLocal++ has found practical use in real-world and industrial settings, demonstrating the flexibility and adaptability of the framework for different applications. In this paper, we position EasyLocal++ within the existing literature by comparing its capabilities with those of available alternative/similar tools. We then trace its history from its initial design 25 years ago to the current version. Furthermore, we describe its architecture, highlighting its design principles and functionalities. We also discuss the features developed to simplify the design of local search methods and enhance their performance. Lastly, we explore potential future perspectives and developments.
References
[1]
Stewart Adcock. 2005. Genetic Algorithms Utility Library (GAUL). (2005). https://gaul.sourceforge.net/ [Accessed: 2024-04-05].
[2]
Alexandre A. Andreatta, Sérgio E.R. Carvalho, and Celso C. Ribeiro. 1998. An object-oriented framework for local search heuristics. In Proceedings. Technology of Object-Oriented Languages. TOOLS 26 (Cat. No.98EX176). IEEE, Santa Barbara, CA, USA, 33--45.
[3]
Davide Armellini, Paolo Borzone, Sara Ceschia, Luca Di Gaspero, and Andrea Schaerf. 2020. Modeling and solving the steelmaking and casting scheduling problem. International Transactions in Operational Research 27, 1 (2020), 57--90.
[4]
Michele Battistutta, Andrea Schaerf, and Tommaso Urli. 2017. Feature-based tuning of single-stage simulated annealing for examination timetabling. Annals of Operations Research 252 (2017), 239--254.
[5]
Ruggero Bellio, Sara Ceschia, Luca Di Gaspero, and Andrea Schaerf. 2021. Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling. Computers & Operations Research 132 (2021), 105300.
[6]
Ruggero Bellio, Sara Ceschia, Luca Di Gaspero, Andrea Schaerf, and Tommaso Urli. 2016. Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Computers & Operations Research 65 (2016), 83--92.
[7]
Stefano Benedettini, Andrea Roli, and Luca Di Gaspero. 2009. EasyGenetic: A Template Metaprogramming Framework for Genetic Master-Slave Algorithms. In Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Second International Workshop, SLS 2009, Brussels, Belgium, September 3-4, 2009. Proceedings, Thomas Stützle, Mauro Birattari, and Holger H. Hoos (Eds.). Lecture Notes in Computer Science, Vol. 5752. Springer-Verlag, Berlin-Heidelberg, Germany, 135--139.
[8]
Julian Blank and Kalyanmoy Deb. 2020. pymoo: Multi-Objective Optimization in Python. IEEE Access 8 (2020), 89497--89509.
[9]
Grady Booch. 1993. Object-Oriented Analysis and Design with Applications (2nd Ed.). Benjamin-Cummings Publishing Co., Inc., USA.
[10]
Edmund K Burke and Yuri Bykov. 2017. The late acceptance hill-climbing heuristic. European Journal of Operational Research 258, 1 (2017), 70--78.
[11]
Mats Carlsson, Sara Ceschia, Luca Di Gaspero, Rasmus Mikkelsen, Andrea Schaerf, and Thomas Stidsen. 2023. Exact and metaheuristic methods for a real-world examination timetabling problem. Journal of Scheduling 26 (2023), 353--367.
[12]
Sara Ceschia, Luca Di Gaspero, Vincenzo Mazzaracchio, Giuseppe Policante, and Andrea Schaerf. 2023. Solving a real-world nurse rostering problem by Simulated Annealing. Operations Research for Health Care 36 (2023), 100379.
[13]
Sara Ceschia, Luca Di Gaspero, Roberto Maria Rosati, and Andrea Schaerf. 2021. Multi-Neighborhood Simulated Annealing for the Minimum Interference Frequency Assignment Problem. EURO Journal on Computational Optimization 10 (2021), 1--32.
[14]
Sara Ceschia, Luca Di Gaspero, Roberto Maria Rosati, and Andrea Schaerf. 2024. Reinforcement Learning for Multi-Neighborhood Local Search in Combinatorial Optimization. In Machine Learning, Optimization, and Data Science, Giuseppe Nicosia, Varun Ojha, Emanuele La Malfa, Gabriele La Malfa, Panos M. Pardalos, and Renato Umeton (Eds.). Springer Nature Switzerland, Cham, 206--221.
[15]
Sara Ceschia, Luca Di Gaspero, and Andrea Schaerf. 2017. Solving Discrete Lot-Sizing and Scheduling by Simulated Annealing and Mixed Integer Programming. Computers & Industrial Engineering 114 (2017), 235--243.
[16]
Sara Ceschia, Luca Di Gaspero, and Andrea Schaerf. 2023. Simulated Annealing for the Home Healthcare Routing and Scheduling Problem. In AIxIA 2022 - Advances in Artificial Intelligence: XXIst International Conference of the Italian Association for Artificial Intelligence, AIxIA 2022, Udine, Italy, November 28 -- December 2, 2022, Proceedings (Udine, Italy). Springer-Verlag, Berlin, Heidelberg, 402--412.
[17]
Sara Ceschia, Luca Di Gaspero, and Andrea Schaerf. 2023. Simulated Annealing for the Home Healthcare Routing and Scheduling Problem. In AIxIA 2022 - Advances in Artificial Intelligence, Agostino Dovier, Angelo Montanari, and Andrea Orlandini (Eds.). Springer International Publishing, Cham, 402--412.
[18]
Sara Ceschia, Rosita Guido, and Andrea Schaerf. 2020. Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods. Annals of Operations Research 288 (2020), 95--113.
[19]
Sara Ceschia, Kevin Roitero, Gianluca Demartini, Stefano Mizzaro, Luca Di Gaspero, and Andrea Schaerf. 2022. Task design in complex crowdsourcing experiments: Item assignment optimization. Computers & Operations Research 148 (2022), 105995.
[20]
Sara Ceschia and Andrea Schaerf. 2013. Local search for a multi-drop multicontainer loading problem. Journal of Heuristics 19, 2 (2013), 275--294.
[21]
Sara Ceschia and Andrea Schaerf. 2016. Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays. Journal of Scheduling 19, 4 (2016), 377--389.
[22]
Sara Ceschia and Andrea Schaerf. 2024. Multi-neighborhood simulated annealing for the capacitated facility location problem with customer incompatibilities. Computers & Industrial Engineering 188 (2024), 109858.
[23]
Raffaele Cipriano, Luca Di Gaspero, and Agostino Dovier. 2013. A Multi-paradigm Tool for Large Neighborhood Search. Springer Berlin Heidelberg, Berlin, Heidelberg, 389--414.
[24]
Francesca Da Ros and Luca Di Gaspero. 2023. Exploring the Potential of JuLeS: A White Box Framework for Local Search Metaheuristics. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (Lisbon, Portugal) (GECCO '23 Companion). Association for Computing Machinery, New York, NY, USA, 191--194.
[25]
Francesca Da Ros and Luca Di Gaspero. 2023. Local Search Strategies for Multi-Objective Flowshop Scheduling: Introducing Pareto Late Acceptance Hill Climbing. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (Lisbon, Portugal) (GECCO '23 Companion). Association for Computing Machinery, New York, NY, USA, 61--62.
[26]
Francesca Da Ros, Luca Di Gaspero, Kevin Roitero, David La Barbera, Stefano Mizzaro, Vincenzo Della Mea, Francesca Valent, and Laura Deroma. 2024. Supporting Fair and Efficient Emergency Medical Services in a Large Heterogeneous Region. Journal of Healthcare Informatics Research (2024), 1--38.
[27]
Kalyanmoy Deb, Ashish Anand, and Dhiraj Joshi. 2002. A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization. Evolutionary Computation 10, 4 (12 2002), 371--395.
[28]
Luca Di Gaspero, Giacomo Di Tollo, Andrea Roli, and Andrea Schaerf. 2007. Hybrid Local Search for Constrained Financial Portfolio Selection Problems. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 4th International Conference, CPAIOR 2007, Brussels, Belgium, May 23--26, 2007, Proceedings, Pascal Van Hentenryck and Laurence Wolsey (Eds.). Lecture Notes in Computer Science, Vol. 4510. Springer Verlag, Berlin, Heidelberg, 44--58.
[29]
Luca Di Gaspero and Andrea Roli. 2009. Flexible Stochastic Local Search for Haplotype Inference. In Learning and Intelligent Optimization, Thomas Stützle (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 74--88.
[30]
Luca Di Gaspero, Andrea Roli, and Andrea Schaerf. 2008. EasyAnalyzer: an object-oriented frameowrk for the experimental analysis of stochastic local search algorithms. In Proceedings of the 15th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (CEUR Workshop Proceedings), Marco Gavanelli and Toni Mancini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 76--90.
[31]
Luca Di Gaspero and Andrea Schaerf. 2001. EasyLocal++: An object-oriented framework for the design of Local Search Algorithms and Metaheuristics. In Proceedings of the 4th Metaheuristics International Conference (MIC-2001), Vol. 2. Porto, Portugal, 287--292.
[32]
Luca Di Gaspero and Andrea Schaerf. 2002. Writing local search algorithms using EASYLOCAL++. In Optimization Software Class Libraries. Springer, Boston, MA, 155--175.
[33]
Luca Di Gaspero and Andrea Schaerf. 2003. EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software --- Practice & Experience 33, 8 (July 2003), 733--765.
[34]
Luca Di Gaspero and Andrea Schaerf. 2006. Neighborhood Portfolio Approach for Local Search applied to Timetabling Problems. Journal of Mathematical Modeling and Algorithms 5, 1 (2006), 65--89.
[35]
Luca Di Gaspero and Andrea Schaerf. 2007. A Composite-Neighborhood Tabu Search Approach to the Traveling Tournament Problem. Journal of Heuristics 13, 2 (April 2007), 189--207.
[36]
Luca Di Gaspero and Andrea Schaerf. 2007. EasySyn++: A Tool for Automatic Synthesis of Stochastic Local Search Algorithms. In Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, International Workshop, SLS 2007, Brussels, Belgium, September 6--8, 2007, Proceedings, Thomas Stützle, Mauro Birattari, and Holger H. Hoos (Eds.). Springer Verlag, Berlin-Heidelberg, Germany, 177--181.
[37]
Marco Dorigo and Thomas Stützle. 2004. Ant Colony Optimization. The MIT Press.
[38]
Johann Dreo, Arnaud Liefooghe, Sébastien Verel, Marc Schoenauer, Juan J. Merelo, Alexandre Quemy, Benjamin Bouvier, and Jan Gmys. 2021. Paradiseo: From a Modular Framework for Evolutionary Computation to the Automated Design of Metaheuristics: 22 Years of Paradiseo. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, New York, NY, USA, 1522--1530.
[39]
Juan J. Durillo and Antonio J. Nebro. 2011. jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software 42, 10 (2011), 760--771.
[40]
Andreas Fink and Stefan Voß. 2002. HotFrame: A heuristic optimization framework. In Optimization Software Class Libraries. Kluwer Academic Publishers, 81--154.
[41]
Carlos Fonseca and Alexandre Jesus. 2023. SIGEVO Summer School 2023 Modelling Projects. https://github.com/cmfonseca/s3-2023. [Accessed: 2024-04-05].
[42]
Alberto Franzin and Thomas Stützle. 2019. Revisiting simulated annealing: A component-based analysis. Computers & Operations Research 104 (2019), 191--206.
[43]
Fred Glover and Manuel Laguna. 1997. Tabu Search. Kluwer Academic Publishers, Boston, MA.
[44]
HeuristicLab 2024. https://github.com/heal-research/HeuristicLab [Accessed: 2024-04-05].
[45]
Hexaly 2024. https://www.hexaly.com/ [Accessed: 2024-04-05].
[46]
John H. Holland. 1992. Genetic Algorithms. Scientific American 267, 1 (1992), 66--73.
[47]
Holger H. Hoos. 2012. Programming by optimization. Commun. ACM 55, 2 (feb 2012), 70--80.
[48]
Scott Kirkpatrick, Daniel Gelatt, and Mario Vecchi. 1983. Optimization by simulated annealing. Science 220 (1983), 671--680.
[49]
Scott Kirkpatrick, Daniel Gelatt, and Mario P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220, 4598 (1983), 671--680.
[50]
Maria Amélia Lopes Silva, Sérgio Ricardo de Souza, Marcone Jamilson Freitas Souza, and Moacir Felizardo de França Filho. 2018. Hybrid metaheuristics and multi-agent systems for solving optimization problems: A review of frameworks and a comparative analysis. Applied Soft Computing 71 (2018), 433--459.
[51]
Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. 2016. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives 3 (2016), 43--58.
[52]
Helena R Lourenço, Olivier C Martin, and Thomas Stützle. 2003. Iterated local search. In Handbook of metaheuristics. Springer, 320--353.
[53]
Modern GALib 2024. https://github.com/s-martin/galib [Accessed: 2024-04-05].
[54]
Federico Pagnozzi and Thomas Stützle. 2019. Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems. European Journal of Operational Research 276, 2 (2019), 409--421.
[55]
JoséAntonio Parejo, Antonio Ruiz-Cortés, Sebastián Lozano, and Pablo Fernandez. 2012. Metaheuristic optimization frameworks: a survey and benchmarking. Soft Computing 16, 3 (2012), 527--561.
[56]
Pierre Schaus, Renaud De Landtsheer. 2016. OscaR User-guide. https://www.info.ucl.ac.be/~pschaus/oscardoc/ [Accessed: 2024-04-05].
[57]
Wolfgang Pree. 1994. Meta patterns --- A means for capturing the essentials of reusable object-oriented design. In Object-Oriented Programming, Mario Tokoro and Remo Pareschi (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 150--162.
[58]
Aurora Ramírez, Rafael Barbudo, and José Raúl Romero. 2023. An experimental comparison of metaheuristic frameworks for multi-objective optimization. Expert Systems 40, 4 (2023), e12672.
[59]
Paolo Rinaldin. 2003. JEasyLocal: Refactoring, riprogettazione e sviluppo di un framework orientato agli oggetti per la ricerca locale. Master thesis (in Italian).
[60]
Roberto Maria Rosati, Matteo Petris, Luca Di Gaspero, and Andrea Schaerf. 2022. Multi-neighborhood simulated annealing for the sports timetabling competition ITC2021. Journal of Scheduling 25, 3 (2022), 301--319.
[61]
Andrea Schaerf, Marco Cadoli, and Maurizio Lenzerini. 2000. LOCAL++: A C++ framework for local search algorithms. Software: Practice and Experience 30, 3 (2000), 233--257.
[62]
Eric O. Scott and Sean Luke. 2019. ECJ at 20: toward a general metaheuristics toolkit. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (Prague, Czech Republic) (GECCO '19). Association for Computing Machinery, New York, NY, USA, 1391--1398.
[63]
Jerry Swan, Steven Adriaensen, Mohamed Bishr, Edmund K. Burke, John A. Clark, Patrick De Causmaecker, Juanjo Durillo, Kevin Hammond, Emma Hart, Colin G. Johnson, Zoltan A. Kocsis, Ben Kovitz, Krzysztof Krawiec, Simon Martin, J. J. Merelo, Leandro L. Minku, Ender Özcan, Gisele L. Pappa, Erwin Pesch, Pablo Garcia-Sànchez, Andrea Schaerf, Kevin Sim, Jim Smith, Thomas Stützle, Vo Stefan, Stefan Wagner, and Xin Yao. 2015. A Research Agenda for Metaheuristic Standardization. In Proceedings of the XI metaheuristics international conference (MIC 2015). Agadir, June 7--10, 2015, 1--3. MIC 2015: the XI Metaheuristics International Conference ; Conference date: 07-06-2015 Through 10-06-2015.
[64]
Jerry Swan, Steven Adriaensen, Alexander E.I. Brownlee, Kevin Hammond, Colin G. Johnson, Ahmed Kheiri, Faustyna Krawiec, J.J. Merelo, Leandro L. Minku, Ender Özcan, Gisele L. Pappa, Pablo García-Sánchez, Kenneth Sörensen, Stefan Voß, Markus Wagner, and David R. White. 2022. Metaheuristics "In the Large". European Journal of Operational Research 297, 2 (2022), 393--406.
[65]
Jerry Swan, Steven Adriænsen, Adam D. Barwell, Kevin Hammond, and David R. White. 2019. Extending the "Open-Closed Principle" to Automated Algorithm Configuration. Evolutionary Computation 27, 1 (03 2019), 173--193.
[66]
Rodrigo F. Toso and Mauricio Resende. 2015. A C++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software 30 (01 2015), 81--93.
[67]
Tommaso Urli. 2014. Hybrid meta-heuristics for combinatorial optimization. Ph.D. Dissertation. Università degli Studi di Udine.
[68]
Rob J.M. Vaessens, Emile H.L. Aarts, and Jan K. Lenstra. 1998. A local search template. Computers & Operations Research 25, 11 (1998), 969--979.
[69]
David Van Bulck, Dries Goossens, and Andrea Schaerf. 2023. Multineighbourhood simulated annealing for the ITC-2007 capacitated examination timetabling problem. Journal of Scheduling (2023), 1--16.
[70]
Stefan Voß and David L Woodruff. 2002. Optimization software class libraries. Springer.
[71]
Matthew B. Wall. 1996. A Genetic Algorithm for Resource-Constrained Scheduling. Ph. D. Dissertation. MIT Mechanical Engineering Department.
[72]
David H. Wolpert and William G. Macready. 1997. No free lunch theorems for optimization. IEEE Trans. on Evo. Comp. 1, 1 (1997), 67--82.
[73]
Eugenia Zanazzo, Sara Ceschia, Agostino Dovier, and Andrea Schaerf. 2024. Solving the medical student scheduling problem using simulated annealing. Journal of Scheduling (2024), 1--14.
Index Terms
- EasyLocal++ a 25-year Perspective on Local Search Frameworks: The Evolution of a Tool for the Design of Local Search Algorithm
Recommendations
Exploring the Potential of JuLeS: A White Box Framework for Local Search Metaheuristics
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary ComputationThe JuLeS framework (short for Julia Local Search)1 is a versatile and highly customizable platform for quickly creating Local Search solvers. Developed using the Julia programming language, JuLeS enables efficient implementation of solvers, ...
Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming
In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-...
Multiple local searches to balance intensification and diversification in a memetic algorithm for the linear ordering problem
HAIS'11: Proceedings of the 6th international conference on Hybrid artificial intelligent systems - Volume Part IIThe Linear Ordering problem (LOP) is an NP-hard problem, which has been solved using different metaheuristic approaches. The best solution for this problem is a memetic algorithm, which uses the traditional approach of hybridizing a genetic algorithm ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
2187 pages
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Università degli Studi di Udine
Conference
GECCO '24 Companion
Sponsor:
GECCO '24 Companion: Genetic and Evolutionary Computation Conference Companion
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 143Total Downloads
- Downloads (Last 12 months)143
- Downloads (Last 6 weeks)53
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in