Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I am looking for papers (or any resources) that go deep into the details of implementing local search algorithms.
I don't want an introductory paper on the subject. Rather, I would prefer a survey dedicated to the implementation issues or papers that go into the details of implementation on a given optimization problem.
N.B : I would appreciate papers with code but detailed papers with no code will be also good
Below are some papers from LocalSolver team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details:
T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2011). Randomized local search for real-life inventory routing. Transportation Science 45(3), pp. 381-398. pdf (extended version pdf)
F. Gardi, K. Nouioua (2011). Local search for mixed-integer nonlinear optimization: a methodology and an application. In Proceedings of EvoCOP 2011, the 11th European Conference on Evolutionary Computation in Combinatorial Optimisation (P. Merz, J.-K. Hao, eds.), Lecture Notes in Computer Science 6622, pp. 167-178. Springer, Berlin, Germany. pdf
B. Estellon, F. Gardi, K. Nouioua (2009). High-performance local search for task scheduling with human resource allocation. In Proceedings of SLS 2009, the 2nd International Workshop on Engineering Stochastic Local Search Algorithms (T. Stützle, M. Birattari, H.H. Hoos, eds.), Lecture Notes in Computer Science 5752, pp. 1-15. Springer, Berlin, Germany. pdf pdf
B. Estellon, F. Gardi, K. Nouioua (2008). Two local search approaches for solving real-life car sequencing problems. In Special Issue: The Car Sequencing Problem (C. Solnon, V.D. Cung, A. Nguyen, C. Artigues, eds.), European Journal of Operational Research 191(3), pp. 928-944. pdf
B. Estellon, F. Gardi, K. Nouioua (2006). Large neighborhood improvements for solving car sequencing problems. In Special Issue: Journées Francophones de Programmation par Contraintes 2005 (F. Fages, N. Jussien, C. Solnon, eds.), RAIRO Operations Research 40(4), pp. 355-379. pdf
These research works have inspired the development of LocalSolver.
I'm not an expert in the field, but the paper An effective implementation of the Lin-Kernighan traveling salesman heuristic by Keld Helsgaun was mentioned in another question before.
This answer focuses on the "papers that go into the details of implementation on a given optimization problem" part of the question.
In "Variable neighborhood search for the $p$-median" by P. Hansen and N. Mladenovic, they go into quite some detail about how to efficiently implement an interchange heuristic originally proposed in Whitaker (1983) for the $p$-median problem. You have to go to the appendix of the paper by Hansen and Mladenocic to get the details of the implementation (no code, just pseudo-code).
Blot et al. (2018)1 did an extensive literature review on multi-objective LS algorithms. You may wish to take a look at Ishibuchi and Murata (2004)2 which focuses on issues in evolutionary algorithms.
These were found through a very quick search using allintitle: survey OR review OR issue "local search" but the query can be broadened as needed.
References
[1] Blot, A., Kessaci, M-É., Jourdan, L. (2018). Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation. Journal of Heuristics. 24(6):853-877.
[2] Ishibuchi, H., Narukawa, K. (2004). Some Issues on the Implementation of Local Search in Evolutionary Multiobjective Optimization. In Genetic and Evolutionary Computation Conference (pp. 1246-1258). Springer, Berlin, Heidelberg.
For what it's worth, here you can download our paper on Multithreaded Incremental Solving for Local Search (not to be confused with multi-walk solving (AKA multi-bet solving), multi-tentant solving or multithreaded partitioned solving), which made our Local Search algorithms up to 3 times faster on 4 cores.
