Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

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.     

Symmetry Breaking Revisited

Symmetries in constraint satisfaction problems (CSPs) are one of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of the search tree. This method can be seen as an improvement of the SBDD method presented by Focacci and Milano [7] and Fahle, Schamberger and Sellmann [5]. We present a simple formalization of our method for which we prove correctness and completeness results. We show that our method is theoretically more efficient as the size of each no-good is smaller. This theoretical analysis is confirmed by thorough experimental evaluation on highly symmetrical real world problems. We are able to break all symmetries for problems with more than 10⁷⁸ symmetries.     

Static and dynamic structural symmetry breaking

We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.     

Predicting and Detecting Symmetries in FOL Finite Model Search

Symmetries abound in logically formulated problems where many axioms are universally quantified, as this is the case in equational theories. Two complementary approaches have been used so far to dynamically tackle those symmetries: prediction and detection. The best-known predictive symmetry elimination method is the least number heuristic (lnh). A more recent predictive method, the extended least number heuristic (xlnh), focuses first on the enumeration of a bijection in the problem and easily exploits in the sequel the remaining isomorphisms. On the other hand, dynamic symmetry detection is costly in the general case (the problem is Graph Iso complete) but allows one to exploit more symmetries, and efficient (polytime) yet incomplete detection algorithms can be used on each node. This paper presents a generalization of xlnh that focuses on the enumeration of a unary function that does not require the function to be bijective, a general notion of symmetry for finite-model search in first-order logic together with an efficient symmetry detection algorithm, and a function-ordering heuristic that exploits the inherent structure of first-order logic theories to improve the search when using function-centric methods. A comprehensive study of the compared efficiency of all methods, in isolation and in combination, demonstrates the acceleration that can be expected in all cases. These ideas are implemented by using the known system SEM as an experimentation framework, to allow for accurate comparisons.     

Skeleton-based intrinsic symmetry detection on point clouds

We present a skeleton-based algorithm for intrinsic symmetry detection on imperfect 3D point cloud data. The data imperfections such as noise and incompleteness make it difficult to reliably compute geodesic distances, which play essential roles in existing intrinsic symmetry detection algorithms. In this paper, we leverage recent advances in curve skeleton extraction from point clouds for symmetry detection. Our method exploits the properties of curve skeletons, such as homotopy to the input shape, approximate isometry-invariance, and skeleton-to-surface mapping, for the detection task. Starting from a curve skeleton extracted from an input point cloud, we first compute symmetry electors, each of which is composed of a set of skeleton node pairs pruned with a cascade of symmetry filters. The electors are used to vote for symmetric node pairs indicating the symmetry map on the skeleton. A symmetry correspondence matrix (SCM) is constructed for the input point cloud through transferring the symmetry map from skeleton to point cloud. The final symmetry regions on the point cloud are detected via spectral analysis over the SCM. Experiments on raw point clouds, captured by a 3D scanner or the Microsoft Kinect, demonstrate the robustness of our algorithm. We also apply our method to repair incomplete scans based on the detected intrinsic symmetries.     

Analytic normal forms and symmetries of strict feedforward control systems

This paper deals with the problem of convergence of normal forms of control systems. We identify an n‐dimensional subclass of control systems, called special strict feedforward form, shortly (SSFF), possessing a normal form which is a smooth (resp. analytic) counterpart of the formal normal form of Kang. We provide a constructive algorithm and illustrate by several examples including the Kapitsa pendulum and the cart–pole system. The second part of the paper is concerned about symmetries of single‐input control systems. We show that any symmetry of a smooth system in SSFF is conjugated to a scaling translation and any 1‐parameter family of symmetries is conjugated to a family of scaling translations along the first variable. We compute explicitly those symmetries by finding the conjugating diffeomorphism. We illustrate our results by computing the symmetries of the cart–pole system. Copyright © 2009 John Wiley & Sons, Ltd.     

Partial symmetry breaking by local search in the group

The presence of symmetry in constraint satisfaction problems can cause a great deal of wasted search effort, and several methods for breaking symmetries have been reported. In this paper we describe a new method called Symmetry Breaking by Nonstationary Optimisation, which interleaves local search in the symmetry group with backtrack search on the constraint problem. It can be tuned to break each symmetry with an arbitrarily high probability with high runtime overhead, or as a lightweight but still powerful method with low runtime overhead. It has negligible memory requirement, it combines well with static lex-leader constraints, and its benefit increases with problem hardness.     

Vector Symmetry Reduction

Symmetry reduction is an effective state-space reduction technique for model checking, and works by restricting search to equivalence class representatives with respect to a group of symmetries for a model. A major problem with symmetry reduction techniques is the time taken to compute the representative of a state, which can be prohibitive. In efficient implementations of symmetry reduction, a symmetry is applied to a state as a sequence of operations which swap component identities. We show that vector processing technology, common to modern computers, can be used to implement a vectorised swap operation, which can be incorporated into the representative computation algorithm to accelerate symmetry reduction. Via a worked example, we present details of this vector symmetry reduction method. We have implemented our techniques in the TopSpin symmetry reduction package for the Spin model checker, and present experimental results showing the speedups obtained via vectorisation for two case-studies running on a PowerPC vector processor.     

A symbolic algorithm for computing recursion operators of nonlinear partial differential equations

A recursion operator is an integro-differential operator which maps a generalized symmetry of a nonlinear partial differential equation (PDE) to a new symmetry. Therefore, the existence of a recursion operator guarantees that the PDE has infinitely many higher-order symmetries, which is a key feature of complete integrability. Completely integrable nonlinear PDEs have a bi-Hamiltonian structure and a Lax pair; they can also be solved with the inverse scattering transform and admit soliton solutions of any order.

A straightforward method for the symbolic computation of polynomial recursion operators of nonlinear PDEs in (1+1) dimensions is presented. Based on conserved densities and generalized symmetries, a candidate recursion operator is built from a linear combination of scaling invariant terms with undetermined coefficients. The candidate recursion operator is substituted into its defining equation and the resulting linear system for the undetermined coefficients is solved.

The method is algorithmic and is implemented in Mathematica. The resulting symbolic package PDERecursionOperator.m can be used to test the complete integrability of polynomial PDEs that can be written as nonlinear evolution equations. With PDERecursionOperator.m, recursion operators were obtained for several well-known nonlinear PDEs from mathematical physics and soliton theory.     

3-D Symmetry Detection and Analysis Using the Pseudo-polar Fourier Transform

Symmetry detection and analysis in 3D images is a fundamental task in a gamut of scientific fields such as computer vision, medical imaging and pattern recognition to name a few. In this work, we present a computational approach to 3D symmetry detection and analysis. Our analysis is conducted in the Fourier domain using the pseudo-polar Fourier transform. The pseudo-polar representation enables to efficiently and accurately analyze angular volumetric properties such as rotational symmetries. Our algorithm is based on the analysis of the angular correspondence rate of the given volume and its rotated and rotated-inverted replicas in their pseudo-polar representations. We also derive a novel rigorous analysis of the inherent constraints of 3D symmetries via groups-theory based analysis. Thus, our algorithm starts by detecting the rotational symmetry group of a given volume, and the rigorous analysis results pave the way to detect the rest of the symmetries. The complexity of the algorithm is O(N ³log (N)), where N×N×N is the volumetric size in each direction. This complexity is independent of the number of the detected symmetries. We experimentally verified our approach by applying it to synthetic as well as real 3D objects.     

Symmetries,almost symmetries,and lazy clause generation

Lazy Clause Generation is a powerful approach for reducing search in Constraint Programming. This is achieved by recording sets of domain restrictions that previously led to failure as new clausal propagators. Symmetry breaking approaches are also powerful methods for reducing search by avoiding the exploration of symmetric parts of the search space. In this paper, we show how we can successfully combine Symmetry Breaking During Search and Lazy Clause Generation to create a new symmetry breaking method which we call SBDS-1UIP. We show that the more precise nogoods generated by a lazy clause solver allow our combined approach to exploit symmetries that cannot be exploited by any previous symmetry breaking method. We also show that SBDS-1UIP can easily be modified to exploit almost symmetries very effectively.     

Skeleton‐Intrinsic Symmetrization of Shapes

Enhancing the self‐symmetry of a shape is of fundamental aesthetic virtue. In this paper, we are interested in recovering the aesthetics of intrinsic reflection symmetries, where an asymmetric shape is symmetrized while keeping its general pose and perceived dynamics. The key challenge to intrinsic symmetrization is that the input shape has only approximate reflection symmetries, possibly far from perfect. The main premise of our work is that curve skeletons provide a concise and effective shape abstraction for analyzing approximate intrinsic symmetries as well as symmetrization. By measuring intrinsic distances over a curve skeleton for symmetry analysis, symmetrizing the skeleton, and then propagating the symmetrization from skeleton to shape, our approach to shape symmetrization is skeleton‐intrinsic. Specifically, given an input shape and an extracted curve skeleton, we introduce the notion of a backbone as the path in the skeleton graph about which a self‐matching of the input shape is optimal. We define an objective function for the reflective self‐matching and develop an algorithm based on genetic programming to solve the global search problem for the backbone. The extracted backbone then guides the symmetrization of the skeleton, which in turn, guides the symmetrization of the whole shape. We show numerous intrinsic symmetrization results of hand drawn sketches and artist‐modeled or reconstructed 3D shapes, as well as several applications of skeleton‐intrinsic symmetrization of shapes.     

Intrinsic Symmetry Detection on 3D Models with Skeleton‐guided Combination of Extrinsic Symmetries

The existing methods for intrinsic symmetry detection on 3D models always need complex measures such as geodesic distances for describing intrinsic geometry and statistical computation for finding non‐rigid transformations to associate symmetrical shapes. They are expensive, may miss symmetries, and cannot guarantee their obtained symmetrical parts in high quality. We observe that only extrinsic symmetries exist between convex shapes, and two intrinsically symmetric shapes can be determined if their belonged convex sub‐shapes are symmetrical to each other correspondingly and connected in a similar topological structure. Thus, we propose to decompose the model into convex parts, and use the similar structures of the skeleton of the model to guide combination of extrinsic symmetries between convex parts for intrinsic symmetry detection. In this way, we give up statistical computation for intrinsic symmetry detection, and avoid complex measures for describing intrinsic geometry. With the similar structures being from small to large gradually, we can quickly detect multi‐scale partial intrinsic symmetries in a bottom up manner. Benefited from the well segmented convex parts, our obtained symmetrical parts are in high quality. Experimental results show that our method can find many more symmetries and runs much faster than the existing methods, even by several orders of magnitude.     

Conjugate symmetry

Conjugate symmetry is an entirely new approach to symmetric Boolean functions that can be used to extend existing methods for handling symmetric functions to a much wider class of functions. These are functions that currently appear to have no symmetries of any kind. Conjugate symmetries occur widely in practice. In fact, we show that even the simplest circuits exhibit conjugate symmetry. To demonstrate the effectiveness of conjugate symmetry we modify an existing simulation algorithm, the hyperlinear algorithm, to take advantage of conjugate symmetry. This algorithm can simulate symmetric functions faster than non-symmetric ones, but due to the rarity of symmetric functions, this optimization is of limited benefit. Because the standard benchmark circuits contain many symmetries it is possible to simulate these circuits faster than is possible with the fastest known event-driven algorithm. The detection and exploitation of conjugate symmetries makes use of GF(2) matrices. It is likely that conjugate symmetry and GF(2) matrices will find applications in many other areas of EDA.     

Detection of rotational and involutional symmetries and congruity of polyhedra

We propose a simple and efficient general algorithm for determining both rotational and involutional symmetries of polyhedra. It requiresO(m ²) time and usesO(m) space, wherem is the number of edges of the polyhedron. As this is the lower bound of the symmetry detection problem for the considered output form, our algorithm is optimal. We show that a slight modification of our symmetry detection algorithm can be used to solve the related conguity problem of polyhedra.     

Tractability through symmetries in propositional calculus

Many propositional calculus problems — for example the Ramsey or the pigeon-hole problems — can quite naturally be represented by a small set of first-order logical clauses which becomes a very large set of propositional clauses when we substitute the variables by the constants of the domainD. In many cases the set of clauses contains several symmetries, i.e. the set of clauses remains invariant under certain permutations of variable names. We show how we can shorten the proof of such problems. We first present an algorithm which detects the symmetries and then we explain how the symmetries are introduced and used in the following methods: SLRI, Davis and Putnam and semantic evaluation. Symmetries have been used to obtain results on many known problems, such as the pigeonhole, Schur's lemma, Ramsey's, the eight queen, etc. The most interesting one is that we have been able to prove for the first time the unsatisfiability of Ramsey's problem (17 vertices and three colors) which has been the subject of much research.     

On the constructive orbit problem

Symmetry reduction techniques aim to combat the state-space explosion problem for model checking by restricting search to representative states from equivalence classes with respect to a group of symmetries. The standard approach to representative computation involves converting a state to its minimal image under a permutation group G, before storing the state. This is known as the constructive orbit problem (COP), and is NP{\mathit{NP}} hard. It may be possible to solve the COP efficiently if G is known to have certain structural properties: in particular if G is isomorphic to a full symmetry group, or G is a disjoint/wreath product of subgroups. We extend existing results on solving the COP efficiently for fully symmetric groups, and investigate the problem of automatically classifying an arbitrary permutation group as a disjoint/wreath product of subgroups. We also present an approximate COP strategy based on local search, and some computational group-theoretic optimisations to improve the basic approach of solving the COP by symmetry group enumeration. Experimental results using the TopSPIN symmetry reduction package, which interfaces with the computational group-theoretic system GAP, illustrate the effectiveness of our techniques.     

Combining Symmetry Reduction and Under-Approximation for Symbolic Model Checking

This work presents a collection of methods that integrate symmetry reduction and under-approximation with symbolic model checking in order to reduce space and time. The main objective of these methods is falsification. However, under certain conditions, they can provide verification as well.We first present algorithms that use symmetry reduction to perform on-the-fly model checking for temporal safety properties. These algorithms avoid building the orbit relation and choose representatives on-the-fly while computing the reachable states. We then extend these algorithms to check liveness properties as well. In addition, we introduce an iterative on-the-fly algorithm that builds subsets of the orbit relation rather than the full relation.Our methods are fully automatic once the user supplies some basic information about the symmetry in the verified system. Moreover, the methods are robust and work correctly even if the information supplied by the user is incorrect. Furthermore, the methods return correct results even when the computation of the symmetry reduction has not been completed due to memory or time explosion.We implemented our methods within the IBM model checker Rule-Base and compared their performance to that of RuleBase. In most cases, our algorithms outperformed RuleBase in both time and space.     

Lightweight dynamic symmetry breaking

Symmetries in constraint problems present an opportunity for reducing search. This paper presents Lightweight Dynamic Symmetry Breaking, an automatic symmetry breaking method that is efficient enough to be used as a default, since it never yields a major slowdown while often giving major performance improvements. This is achieved by automatically exploiting certain kinds of symmetry that are common, can be compactly represented, easily and efficiently processed, automatically detected, and lead to large reductions in search. Moreover, the method is easy to implement and integrate in any constraint system. Experimental results show the method is competitive with the best symmetry breaking methods without risking poor performance.