Abstract
One of the most well-known and widely used local search techniques for solving optimization problems in Constraint Programming is the Large Neighborhood Search (LNS) algorithm. Such a technique is, by nature, very flexible and can be easily integrated within standard backtracking procedures. One of its drawbacks is that the relaxation process is quite often problem dependent. Several works have been dedicated to overcome this issue through problem independent parameters. Nevertheless, such generic approaches need to be carefully parameterized at the instance level. In this paper, we demonstrate that the issue of finding a problem independent neighborhood generation technique for LNS can be addressed using explanation-based neighborhoods. An explanation is a subset of constraints and decisions which justifies a solver event such as a domain modification or a conflict. We evaluate our proposal for a set of optimization problems. We show that our approach is at least competitive with or even better than state-of-the-art algorithms and can be easily combined with state-of-the-art neighborhoods. Such results pave the way to a new use of explanation-based approaches for improving search.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Atkins, K.E. (1989). An introduction to numerical analysis.
Cambazard, H, & Jussien, N (2006). Identifying and exploiting problem structures using explanation-based constraint programming. Constraints, 11 (4), 295–313.
Chabrier, A, Danna, E, Le Pape, C, Perron, L (2004). Solving a network design problem. Annals of Operations Research, 130 (1–4), 217–239.
Copado-Méndez, PJ, Blum, C, Guillén-Gosálbez, G, Jiménez, L (2013). Application of large neighborhood search to strategic supply chain management in the chemical industry. In Hybrid metaheuristics (pp. 335–352). Springer.
Danna, E, & Perron, L. (2003). Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs In Rossi, F (Ed.), Principles and practice of constraint programming? Lecture notes in computer science, CP 2003 (Vol. 2833, pp. 817–821). Berlin Heidelberg: Springer.
Debruyne, R, Ferrand, G, Jussien, N, Lesaint, W, Ouis, S, Tessier, A (2003). Correctness of constraint retraction algorithms. In FLAIRS’03: 16th international Florida artificial intelligence research society conference (pp. 172–176). St. Augustine: AAAI press.
Demir, E, Bektaṡ, T, Laporte, G (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research.
Gent, IP., Miguel, I, Moore, N.C.A., Peña, R. (2010). Lazy explanations for constraint propagators. In Carro, M (Ed.), Practical aspects of declarative languages, lecture notes in computer science (Vol 5937 pp. 217–233). Berlin Heidelberg: Springer.
Ginsberg, M. (1993). Dynamic backtracking. Journal of Artificial Intelligence Research, 1, 25–46.
Godard, D, Laborie, P, Nuijten, W (2005). Randomized large neighborhood search for cumulative scheduling. In: ICAPS (Vol. 5, pp. 81–89).
Harvey, W, & Schimpf, J (2002). Bounds consistency techniques for long linear constraints.
Jussien, N., & Lhomme, O. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139 (1), 21–45.
Jussien, N (2003). The versatility of using explanations within constraint programming. Technical Report 03-04-INFO.
Jussien, N, Debruyne, R, Boizumault, P (September 2000). Maintaining arc-consistency within dynamic backtracking. In Principles and practice of constraint programming (CP 2000), lecture notes in computer science (no. 1894 pp. 249–261). Singapore: Springer-Verlag.
Jussien, N, & Lhomme, O (1998). Dynamic domain splitting for numeric csps. In European conference on artificial intelligence (ECAI’98) (pp. 224–228).
Kovacs, AA, Parragh, SN, Doerner, KF, Hartl, RF (2012). Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of scheduling, 15 (5), 579–600.
Laborie, P., & Godard, D. (2007). Self-adapting large neighborhood search:application to single-mode scheduling problems. In P. Baptiste, G. Kendall, A. Munier-Kordon, and F. Sourd (Eds.), Proceedings of the 3rd multidisciplinary international conference on scheduling: theory and applications (MISTA 2007) (pp. 276–284). Paris. Paper.
Mairy, J-B, Deville, Y, Hentenryck, PV (2011). Reinforced adaptive large neighborhood search. In 8th workshop on local search techniques in constraint satisfaction (LSCS2011).
Mairy, J-B, Schaus, P, Deville, Y (2010). Generic adaptive heuristics for large neighborhood search. In 7th workshop on local search techniques in constraint satisfaction (LSCS2010).
Malitsky, Y, Mehta, D, O’Sullivan, B, Simonis, H (2013). Tuning parameters of large neighborhood search for the machine reassignment problem. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 176–192). Springer.
Ohrimenko, O, Stuckey, PJ., Codish, M (2009). Propagation via lazy clause generation. Constraints, 14 (3), 357–391.
Perron, L. (2003). Fast restart policies and large neighborhood search In Rossi, F (Ed.), , Principles and practice of constraint programming at CP 2003, lecture notes in computer science(Vol. 2833). Berlin Heidelberg: Springer.
Perron, L, Shaw, P, Rueher, M. (2004). Combining forces to solve the car sequencing problem In Régin, J-C (Ed.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, lecture notes in computer science (Vol 2833 pp. 225–239). Berlin Heidelberg: Springer.
Perron, L, Shaw, P, Furnon, V (2004). Propagation guided large neighborhood search. In CP’04 (pp. 468–481).
Pisinger, D, & Ropke, S (2010). Large neighborhood search. In Handbook of metaheuristics (pp. 399–419). Springer.
Pralet, C, Verfaillie, G, Rueher, M. (2004). Travelling in the world of local searches in the space of partial assignments. In Régin, J-C (Ed.), , CPAIOR, volume 3011 of lecture notes in computer science, (pp. 240–255): Springer.
Prosser, P. (1995). MAC-CBJ: maintaining arc consistency with conflict-directed backjumping. Technical Report Research Report/95/177. Dept. of Computer Science, University of Strathclyde.
Prud’homme, C, & Fages, J-G (2013). Introduction to choco3. In 1st Workshop on CPSolvers: modeling, applications, integration, and standardization, CP. http://choco.emn.fr.
Roli, A, Benedettini, S, Stützle, T, Blum, C (2012). Large neighbourhood search algorithms for the founder sequence reconstruction problem. Computers & operations research, 39 (2), 213–224.
Schiex, T., & Verfaillie, G. (1994). Nogood recording for static and dynamic constraint satisfaction problem. IJAIT, 3 (2), 187–207.
Shaw, P, & Puget, J-F. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In Maher, M (Ed.), Principles and practice of constraint programming, CP98, lecture notes in computer science ( Vol. 1520 pp. 417–431). Berlin Heidelberg: Springer.
Stuckey, PJ (2010). Lazy clause generation: Combining the power of sat and cp (and mip?) solving. In CPAIOR (pp. 5–9).
Verfaillie, G, & Jussien, N (2005). Constraint solving in uncertain and dynamic environments – a survey. Constraints, 10 (3), 253–281.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Prud’homme, C., Lorca, X. & Jussien, N. Explanation-based large neighborhood search. Constraints 19, 339–379 (2014). https://doi.org/10.1007/s10601-014-9166-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-014-9166-6