Inter-instance nogood learning in constraint programming

Geoffrey Chu, Peter J. Stuckey

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

3 Citations (Scopus)

Abstract

Lazy Clause Generation is a powerful approach to reducing search in Constraint Programming. This is achieved by recording sets of domain restrictions that previously led to failure as new clausal propagators called nogoods. This dramatically reduces the search and provides orders of magnitude speedups on a wide range of problems. Current implementations of Lazy Clause Generation only allows solvers to learn and utilize nogoods within an individual problem. This means that everything the solver learns will be forgotten as soon as the current problem is finished. In this paper, we show how Lazy Clause Generation can be extended so that nogoods learned from one problem can be retained and used to significantly speed up the solution of other, similar problems.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings
PublisherSpringer
Pages238-247
Number of pages10
ISBN (Print)9783642335570
DOIs
Publication statusPublished - 7 Nov 2012
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2012 - Quebec, Canada
Duration: 8 Oct 201212 Oct 2012
Conference number: 18th
http://archive.a4cp.org/cp2012/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7514 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2012
Abbreviated titleCP 2012
CountryCanada
CityQuebec
Period8/10/1212/10/12
Internet address

Cite this