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

Abstract

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
PublisherSpringer
Pages55-71
Number of pages17
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
DOIs
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sep 202011 Sep 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings)
https://cp2020.a4cp.org (Website)

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
CountryBelgium
CityLouvain-la-Neuve
Period7/09/2011/09/20
Internet address

Cite this