Return to search

Propagation redundancy in finite domain constraint satisfaction. / CUHK electronic theses & dissertations collection

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. / Choi Chiu Wo. / "September 2005." / Adviser: Jimmy Lee. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 3890. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 106-117). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_343654
Date January 2005
ContributorsChoi, Chiu Wo., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, theses
Formatelectronic resource, microform, microfiche, 1 online resource (xi, 117 p. : ill.)
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0016 seconds