Many real life problems can naturally be modeled as constraint satisfaction problems (CSPs), which can sometimes contain both variable symmetries and value symmetries. Tree search based CSP solving algorithms often suffer from symmetries, which creates symmetrically equivalent states in the search tree. Exploring more than one of the symmetrically equivalent states is a waste of search efforts. Adding symmetry breaking constraints to a CSP can force the search to visit only one of the symmetrical regions and helps reduce search space. While variable symmetry breaking constraints can be expressed relatively easily and executed efficiently by enforcing lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this thesis, we propose two methods of using symmetry breaking constraints to tackle value symmetries. In the first method, we show theoretically when value symmetries in one CSP model correspond to variable symmetries in another CSP model of the same problem. We also show when variable symmetry breaking constraints in the two models, combined using channeling constraints, are consistent. Such results allow tackling value symmetries efficiently using additional CSP variables and channeling constraints. In the second method, we identify a common and important class of value symmetries, namely symmetries of indistinguishable values, and introduce value precedence to break such symmetries. Although value precedence can be expressed straightforwardly using if-then constraints in existing constraint programming systems, the resulting formulation is inefficient both in terms of size and runtime. We present two propagation algorithms for implementing global constraints on value precedence for integer and set variables respectively. We also characterize the propagation levels attained by various usages of the global constraints and the conditions when the constraints are consistent with variable symmetry breaking constraints. Extensive experiments are conducted to verify the feasibility and efficiency of our two proposals. / Law Yat Chiu. / "September 2005." / Adviser: Jimmy Ho Man Lee. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 3905. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 112-123). / 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. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_343656 |
| Date | January 2005 |
| Contributors | Law, Yat Chiu., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, theses |
| Format | electronic resource, microform, microfiche, 1 online resource (xii, 123 p. : ill.) |
| Rights | Use 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.0026 seconds