NDLI: Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Please wait, while we are loading the content...

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Content Provider	Springer Nature Link
Author	Law, Y. C. Lee, J. H. M.
Copyright Year	2006
Abstract	Constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.
Starting Page	221
Ending Page	267
Page Count	47
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	11
Issue Number	2-3
e-ISSN	15729354
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2006-06-14
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Symmetry breaking Value symmetries Constraint satisfaction Optimization Operations Research/Decision Theory Computing Methodologies Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Symmetry Definitions for Constraint Satisfaction Problems

Dynamic structural symmetry breaking for constraint satisfaction problems

Dominance breaking constraints

Symmetries, almost symmetries, and lazy clause generation

Lightweight dynamic symmetry breaking

Relatively quantified constraint satisfaction

Grammar constraints

High-Order Consistency in Valued Constraint Satisfaction

Partial symmetry breaking by local search in the group

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Similar Documents

Symmetry Definitions for Constraint Satisfaction Problems

Dynamic structural symmetry breaking for constraint satisfaction problems

Dominance breaking constraints

Symmetries, almost symmetries, and lazy clause generation

Lightweight dynamic symmetry breaking

Relatively quantified constraint satisfaction

Grammar constraints

High-Order Consistency in Valued Constraint Satisfaction

Partial symmetry breaking by local search in the group

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction