Automatic triggering of constraint propagation

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

Abstract

A constraint satisfaction problem requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. The main feature of any constraint solver is constraint propagation, it embeds any reasoning which consists in explicitly forbidding values or combinations of values for some variables of a problem because a given subset of its constraints cannot be satisfied otherwise. It is very important to apply constraint propagation as efficiently as possible. In this paper, we present a hybrid solver based on a Branch and Bound algorithm combined with constraint propagation to reduce the search space. Some rules trigger constraint propagation based on some observations of the solving process. The results show that is possible to make reasonable use of constraint propagation.

Original languageEnglish
Title of host publicationComputational Science and Its Applications, ICCSA 2013 - 13th International Conference, Proceedings
PublisherSpringer Verlag
Pages452-461
Number of pages10
EditionPART 5
ISBN (Print)9783642396397
DOIs
StatePublished - 2013
Externally publishedYes
Event13th International Conference on Computational Science and Its Applications, ICCSA 2013 - Ho Chi Minh City, Viet Nam
Duration: 24 Jun 201327 Jun 2013

Publication series

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

Conference

Conference13th International Conference on Computational Science and Its Applications, ICCSA 2013
CountryViet Nam
CityHo Chi Minh City
Period24/06/1327/06/13

Keywords

  • Constraint propagation
  • Constraint Satisfaction Problems
  • Constraint solving

Fingerprint Dive into the research topics of 'Automatic triggering of constraint propagation'. Together they form a unique fingerprint.

Cite this