Solving satisfaction problems using large-neighbourhood search

Gustav Björdal, Pierre Flener, Justin Pearson, Peter J. Stuckey, Guido Tack

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


Large-neighbourhood 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 hard-to-satisfy constraints by replacing them with penalty-function 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 non-failing 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 non-failing without modifying its code. Experimental evaluation shows that non-failing 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 hard-to-satisfy optimisation problems.

Original languageEnglish
Title of host publication26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
EditorsHelmut Simonis
Place of PublicationCham Switzerland
Number of pages17
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sept 202011 Sept 2020
Conference number: 26th (Proceedings) (Website)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
Internet address

Cite this