Abstract/Details

Propagation redundancy in finite domain constraint satisfaction


2006 2006

Other formats: Order a copy

Abstract (summary)

A widely adopted approach to solving constraint satisfaction problems combines backtracking tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model and may offer extra information to enhance constraint propagation. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. In this thesis, we propose propagation rules as a tool to compare the propagation strength of constraints, and establish results relating logical and propagation redundancy.

Redundant constraints arise naturally in the process of redundant modeling, where two models of the same problem are connected and combined through channeling constraints. We characterize channeling constraints in terms of restrictive and unrestrictive channel function and give general theorems for proving propagation redundancy of constraints in the combined model. We illustrate, on problems from CSPLib, how detecting and removing propagation redundant constraints can often significantly speed up constraint-solving.

Indexing (details)


Subject
Artificial intelligence;
Computer science
Classification
0800: Artificial intelligence
0984: Computer science
Identifier / keyword
Applied sciences; Constraint satisfaction; Propagation; Tree search
Title
Propagation redundancy in finite domain constraint satisfaction
Author
Choi, Chiu Wo
Number of pages
117
Publication year
2006
Degree date
2006
School code
1307
Source
DAI-B 67/07, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9780542760358
Advisor
Lee, Jimmy
University/institution
The Chinese University of Hong Kong (Hong Kong)
University location
Hong Kong
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3222669
ProQuest document ID
304908835
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/304908835
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.