Abstract
Largeneighbourhood search (LNS) improves an initial solution, hence it is not directly applicable to satisfaction problems. In order to use LNS in a constraint programming (CP) framework to solve satisfaction problems, we usually soften some hardtosatisfy constraints by replacing them with penaltyfunction constraints. LNS is then used to reduce their penalty to zero, thus satisfying the original problem. However, this can give poor performance as the penalties rarely cause propagation and therefore do not drive each CP search, and by extension the LNS search, towards satisfying the replaced constraints until very late. Our key observation is that entirely replacing a constraint is often overkill, as the propagator for the replaced constraint could have performed some propagation without causing backtracking. We propose the notion of a nonfailing propagator, which is subsumed just before causing a backtrack. We show that, by only making a few changes to an existing CP solver, any propagator can be made nonfailing without modifying its code. Experimental evaluation shows that nonfailing propagators, when used in conjunction with penalties, can greatly improve LNS performance compared to just having penalties. This allows us to leverage the power of the many sophisticated propagators that already exist in CP solvers, in order to use LNS for solving hard satisfaction problems and for finding initial solutions to hardtosatisfy optimisation problems.
Original language  English 

Title of host publication  26th International Conference, CP 2020 LouvainlaNeuve, Belgium, September 7–11, 2020 Proceedings 
Editors  Helmut Simonis 
Place of Publication  Cham Switzerland 
Publisher  Springer 
Pages  5571 
Number of pages  17 
ISBN (Electronic)  9783030584757 
ISBN (Print)  9783030584740 
DOIs  
Publication status  Published  2020 
Event  International Conference on Principles and Practice of Constraint Programming 2020  LouvainlaNeuve, Belgium Duration: 7 Sep 2020 → 11 Sep 2020 Conference number: 26th https://link.springer.com/book/10.1007/9783030584757 (Proceedings) https://cp2020.a4cp.org (Website) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  12333 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Conference on Principles and Practice of Constraint Programming 2020 

Abbreviated title  CP2020 
Country  Belgium 
City  LouvainlaNeuve 
Period  7/09/20 → 11/09/20 
Internet address 
