2026-07-24T11:33:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23881 2025-11-12T13:10:53Z ddc:004 open_access

Dependency-Curated Large Neighbourhood Search Knutar Lewander, Frej Flener, Pierre Pearson, Justin Combinatorial Optimisation Large Neighbourhood Search (LNS) Constraint-Based Local Search (CBLS) In large neighbourhood search (LNS), an incumbent initial solution is incrementally improved by selecting a subset of the variables, called the freeze set, and fixing them to their values in the incumbent solution, while a value for each remaining variable is found and assigned via solving (such as constraint programming-style propagation and search). Much research has been performed on finding generic and problem-specific LNS selection heuristics that select freeze sets that lead to high-quality solutions. In constraint-based local search (CBLS), the relations between the variables via the constraints are fundamental and well-studied, as they capture dependencies of the variables. In this paper, we apply these ideas from CBLS to the LNS context, presenting the novel dependency curation scheme, which exploits them to find a low-cardinality set of variables that the freeze set of any selection heuristic should be a subset of. The scheme often improves the overall performance of generic selection heuristics. Even when the scheme is used with a naïve generic selection heuristic that selects random freeze sets, the performance is competitive with more elaborate generic selection heuristics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frej Knutar Lewander and Pierre Flener and Justin Pearson 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.20 urn:nbn:de:0030-drops-238810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode