Treffer: Solving necklace constraint problems

Title:
Solving necklace constraint problems
Authors:
FLENER, Pierre, PEARSON, Justin
Source:
Journal of algorithms (Print). 64(2-3):61-73
Publisher Information:
San Diego, CA: Elsevier, 2009.
Publication Year:
2009
Physical Description:
print, 32 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Plans d'expériences et configurations, Designs and configurations, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Performances des systèmes informatiques. Fiabilité, Computer systems performance. Reliability, Intelligence artificielle, Artificial intelligence, Résolution de problèmes, jeux, Problem solving, game playing, Brisure symétrie, Symmetry breaking, Ruptura simetría, Contrainte, Constraint, Coacción, Dynamique, Dynamics, Dinámica, Enumération, Enumeration, Enumeración, Horaire, Schedule, Horario, Objet, Object, Objeto, Ordonnancement, Scheduling, Reglamento, Problème combinatoire, Combinatorial problem, Problema combinatorio, Procédure, Procedure, Procedimiento, Rotation, Rotación, Résolution (math), Solving, Resolución (matemática), Résolution problème, Problem solving, Resolución problema, Symétrie, Symmetry, Simetría, 05Bxx, 68M20, 68T20, 68Wxx, Algorithme combinatoire, Combinatorial algorithm, Conception algorithme, Programmation combinatoire, Programmation contrainte, Structure combinatoire, Combinatorial structure, Constraint problem, Necklace, Rotation schedule, Static and dynamic symmetry breaking
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Department of Information Technology, Uppsala University, Box 337, 751 05 Uppsala, Sweden
ISSN:
0196-6774
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=21540176
Rights:
Copyright 2009 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.21540176
Database:
PASCAL Archive

Weitere Informationen

Some constraint problems have a combinatorial structure where the constraints allow the sequence of variables to be rotated (necklaces), if not also the domain values to be permuted (unlabelled necklaces), without getting an essentially different solution. We bring together the fields of combinatorial enumeration, where efficient algorithms have been designed for (special cases of) some of these combinatorial objects, and constraint programming, where the requisite symmetry breaking has at best been done statically so far. We design the first search procedure and identify the first symmetry-breaking constraints for the general case of unlabelled necklaces. Further, we compare dynamic and static symmetry breaking on real-life scheduling problems featuring (unlabelled) necklaces.