Return to search

Weighted constraint satisfaction with set variables.

Siu Fai Keung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 79-83). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- (Weighted) Constraint Satisfaction --- p.1 / Chapter 1.2 --- Set Variables --- p.2 / Chapter 1.3 --- Motivations and Goals --- p.3 / Chapter 1.4 --- Overview of the Thesis --- p.4 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.6 / Chapter 2.1.1 --- Backtracking Tree Search --- p.8 / Chapter 2.1.2 --- Consistency Notions --- p.10 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.14 / Chapter 2.2.1 --- Branch and Bound Search --- p.17 / Chapter 2.2.2 --- Consistency Notions --- p.19 / Chapter 2.3 --- Classical CSPs with Set Variables --- p.23 / Chapter 2.3.1 --- Set Variables and Set Domains --- p.24 / Chapter 2.3.2 --- Set Constraints --- p.24 / Chapter 2.3.3 --- Searching with Set Variables --- p.26 / Chapter 2.3.4 --- Set Bounds Consistency --- p.27 / Chapter 3 --- Weighted Constraint Satisfaction with Set Variables --- p.30 / Chapter 3.1 --- Set Variables --- p.30 / Chapter 3.2 --- Set Domains --- p.31 / Chapter 3.3 --- Set Constraints --- p.31 / Chapter 3.3.1 --- Zero-arity Constraint --- p.33 / Chapter 3.3.2 --- Unary Constraints --- p.33 / Chapter 3.3.3 --- Binary Constraints --- p.36 / Chapter 3.3.4 --- Ternary Constraints --- p.36 / Chapter 3.3.5 --- Cardinality Constraints --- p.37 / Chapter 3.4 --- Characteristics --- p.37 / Chapter 3.4.1 --- Space Complexity --- p.37 / Chapter 3.4.2 --- Generalization --- p.38 / Chapter 4 --- Consistency Notions and Algorithms for Set Variables --- p.41 / Chapter 4.1 --- Consistency Notions --- p.41 / Chapter 4.1.1 --- Element Node Consistency --- p.41 / Chapter 4.1.2 --- Element Arc Consistency --- p.43 / Chapter 4.1.3 --- Element Hyper-arc Consistency --- p.43 / Chapter 4.1.4 --- Weighted Cardinality Consistency --- p.45 / Chapter 4.1.5 --- Weighted Set Bounds Consistency --- p.46 / Chapter 4.2 --- Consistency Enforcing Algorithms --- p.47 / Chapter 4.2.1 --- "Enforcing Element, Node Consistency" --- p.48 / Chapter 4.2.2 --- Enforcing Element Arc Consistency --- p.51 / Chapter 4.2.3 --- Enforcing Element Hyper-arc Consistency --- p.52 / Chapter 4.2.4 --- Enforcing Weighted Cardinality Consistency --- p.54 / Chapter 4.2.5 --- Enforcing Weighted Set Bounds Consistency --- p.56 / Chapter 5 --- Experiments --- p.59 / Chapter 5.1 --- Modeling Set Variables Using 0-1 Variables --- p.60 / Chapter 5.2 --- Softening the Problems --- p.61 / Chapter 5.3 --- Steiner Triple System --- p.62 / Chapter 5.4 --- Social Golfer Problem --- p.63 / Chapter 5.5 --- Discussions --- p.66 / Chapter 6 --- Related Work --- p.68 / Chapter 6.1 --- Other Consistency Notions in WCSPs --- p.68 / Chapter 6.1.1 --- Full Directional Arc Consistency --- p.68 / Chapter 6.1.2 --- Existential Directional Arc Consistency --- p.69 / Chapter 6.2 --- Classical CSPs with Set Variables --- p.70 / Chapter 6.2.1 --- Bounds Reasoning --- p.70 / Chapter 6.2.2 --- Cardinality Reasoning --- p.70 / Chapter 7 --- Concluding Remarks --- p.72 / Chapter 7.1 --- Contributions --- p.72 / Chapter 7.2 --- Future Work --- p.74 / List of Symbols --- p.76 / Bibliography --- p.79

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_325707
Date January 2006
ContributorsSiu, Fai Keung., 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, bibliography
Formatprint, x, 83 leaves : ill. ; 30 cm.
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.0017 seconds