[Homepage]
[Call for Papers]
[Important Dates]
[Organisation]
[Proceedings]
[Programme]
[CP 2006]
[Previous Workshops]
The full proceedings and individual papers can be downloaded from this page. Follow the links to view the abstracts of individual papers.
Complete proceedings - [download]
Reasoning by Dominance in Not-Equals Binary Constraint Networks:
Belaïd Benhamou and Mohamed Réda Saïdi [abstract]
Dynamic Symmetry Breaking Restarted:
Daniel S. Heller and Meinolf Sellmann [abstract]
GAPLex: Generalised Static Symmetry Breaking:
Chris Jefferson, Tom Kelsey, Steve Linton and Karen Petrie [abstract]
Speeding up Weak Symmetry Exploitation for Separable Objectives:
Roland Martin [abstract]
On implementing symmetry detection:
C. Mears and M. Garcia de la Banda and M. Wallace [abstract]
A comparison of SBDS and Dynamic Lex Constraints:
Jean-François Puget [abstract]
Solving Partially Symmetrical CSPs:
F. Verroust and N. Prcovic [abstract]
Symmetry Breaking in Subgraph Pattern Matching:
Stéphane Zampelli, Yves Deville, and Pierre Dupont [abstract]
Dynamic detection and elimination of symmetry in constraints, is in general a hard task, but in "Not-Equals binary constraint networks", the symmetry conditions can be simplified. In this paper, we extend the principle of symmetry to dominance in "Not-Equals Constraint Networks" and show how dominated values are detected and eliminated at each node of the search tree.
A Linear time complexity algorithm which detects the dominated values is proposed. Dominance is exploited in an enumerative method adapted to solve Not-Equals CSPs. This enumerative method augmented by Dominance is experimented on both randomly generated instances of graph coloring and Dimacs graph coloring benchmarks and its performance is compared to the same method augmented by symmetry and to the well known DSATUR method. The obtained results show that reasoning by dominance improves symmetry reasoning and our method outperforms both previous methods in solving graph coloring. [download | top]
Recently, structural symmetry breaking (SSB), a new technique for breaking all piecewise variable and value symmetry in constraint satisfaction problems (CSPs), was introduced. As of today, it is unclear whether the heavy symmetry ltering that SSB performs is at all worthwhile. This paper has two aims: First, we assess the feasibility of SSB. To this end, we introduce the rst random benchmark generator that produces CSP instances with piecewise symmetric variables and values of constrainedness. It allows us to evaluate SSB on different regions of constrainedness. Secondly, we study how symmetry breaking and restarts interact. We propose practical enhancements of SSB that allow us to re-use symmetry no-goods in subsequent restarts efciently. With those enhancements, we nd that symmetry breaking can actually benet from restarts. However, the improvements to be gained by restarting are far smaller than those that can be obtained for methods that break only some symmetries or none at all. Surprisingly, we nd that a combination of restarts and breaking value symmetry only can be competitive with, or even be superior to, complete symmetry breaking. [download | top]
We describe a novel algorithm that statically breaks symmetry in CSPs by using computational group theory during search. This algorithm extends and generalises the commonly used double lex method for breaking symmetry in matrices. We showthat our new symmetry breaking method, GAPLex, is sound (will neither lose solutions nor return incorrect solutions) and complete (will return exactly one member from each class of symmetrically equivalent solutions). We demonstrate that our implementation of GAPLex is competitive with other methods, being effectively applicable to CSPs with large domains and less than full variable and/or value symmetry. We also describe how GAPLex can be combined with incomplete symmetry breaking methods such as double-lex to provide fast and complete symmetry breaking. We believe this to be the rst method that successfully combines the posting of symmetry breaking constraints before search, with symmetry breaking by analysis of search states. [download | top]
We consider an algorithm that enables us to reduce the number of solutions to consider for weakly symmetric problems. The idea is to store partial permutations during the solving process and re-use them for future solutions thereby reducing the number of weakly symmetric solutions to consider for these solutions. The idea can be applied to problems where the weak symmetry is introduced by a separable objective function. We present the theoretical soundness of the idea and a prototype algorithm that could be in-cooperated as a global constraint to the constraint solver. [download | top]
Automatic symmetry detection has received a signicant amount of interest, which has resulted in a large number of proposed methods. This paper reports on our experiences while implementing the approach of [9]. In particular, it proposes a modication of the approach to deal with general expressions, discusses the insights gained, and gives the results of a preliminary experimental evaluation of the accuracy and eciency of the approach. [download | top]
Many symmetry breaking methods have been proposed so far. Previous works have shown that these methods could be combined together under some conditions. We use a dierent angle : we compare the pruning power of two symmetry breaking methods. The rst one is the rather classical SBDS method. The second one is the recently proposed dynamic lex constraints (DLC). We theoretically show that DLC prunes more nodes than SBDS if values are tried in increasing order. We also show experimentally that DLC can be more ecient than SBDS. [download | top]
Many CSPs contain a combination of symmetrical and asymmetrical constraints. We present a global approach that allows to apply any usual methods for breaking symmetries on the symmetrical part of a CSP and then to search for a global solution by integrating afterwards the asymmetrical constraints. Then, we focus on optimization problems where only the cost function is asymmetrical. We show experimentally that in this case we can speed up the search of some problems. [download | top]
Graph pattern matching, a central application in many elds, can be modelled as a CSP. This CSP approach can be competitive with dedicated algorithms. In this paper, we develop symmetry breaking techniques for subgraph matching in order to increase the number of tractable instances. Speci c detection techniques are rst developed for the classical variables symmetries and value symmetries. It is also shown how these symmetries can be broken when solving subgraph matching. We also show how conditional value symmetries can be automatically detected and handled in the search process. Then, the concept of local value symmetries is introduced; it is shown how these symmetries can be computed and exploited. Finally, experimental results show that symmetry breaking is an effective way to increase the number of tractable instances of the subgraph matching problem. [download | top]