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.     

基于对称破坏的子图同构约束求解算法

为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解。实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率。     

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.     

Propagation algorithms for lexicographic ordering constraints

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.     

Search combinators

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.     

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 breaking in population-based optimization

Argues that the performance of evolutionary algorithms working on hard optimization problems depends strongly on how the population breaks the "symmetry" of the search space. The splitting of the search space into widely separate regions containing local optima is a generic property of a large class of hard optimization problem. This phenomenon is discussed by reference to two well studied examples, the Ising perceptron and the satisfiability problem (K-SAT). A finite population will quickly concentrate on one region of the search space. The cost of crossover between solutions in different regions of search space can accelerate this symmetry breaking. This, in turn, can dramatically reduce the amount of exploration, leading to suboptimal solutions being found. An analysis of symmetry breaking using diffusion model techniques borrowed from classical population genetics is presented. This shows how symmetry breaking depends on parameters such as the population size and selection rate.     

Dynamic structural symmetry breaking for constraint satisfaction problems

In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for some classes of CSPs.     

Excluding Symmetries in Constraint-Based Search

We introduce a new method, called symmetry excluding search (SES), for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. The SES-method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or a subset of all symmetries.We proof correctness, completeness and symmetry exclusion properties of our method. Then, we show how to apply the SES-method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.     

Design of Financial CDO Squared Transactions Using Constraint Programming

We give an approximate and often extremely fast method of building a particular kind of portfolio in finance, here called a portfolio design (PD), with applications in the credit derivatives market, for example when designing collateralised debt obligations squared (CDO²) transactions. A PD generalises a balanced incomplete block design (BIBD) and is usually harder to build. Worse, typical financial PDs are an order of magnitude larger than the largest BIBDs built so far by constraint programs, and in practice an optimisation version of the problem of building PDs has to be solved. Our method is based on embedding small designs, whose determination is itself a constraint satisfaction problem, into the original large design. Together with the detection of when a PD might be a BIBD, symmetry breaking, extended reuse of previously built PDs, and admissibility checking during search, the performance of the method becomes good enough for designing (near-)optimal CDO² transactions, with sizes common in the credit derivatives market, within minutes. For example, we optimally build a typical financial PD, which has over 10⁷⁴⁶ symmetries, in just a few minutes. The high quality of our approximate designs can be assessed by comparison with a lower bound on the optimum. Our designs sufficiently improve the currently best ones so as often to make the difference between having and not having a feasible CDO² transaction due to investor and rating-agency constraints.     

Top-down mining of frequent closed patterns from very high dimensional data

Frequent pattern mining is an essential theme in data mining. Existing algorithms usually use a bottom-up search strategy. However, for very high dimensional data, this strategy cannot fully utilize the minimum support constraint to prune the rowset search space. In this paper, we propose a new method called top-down mining together with a novel row enumeration tree to make full use of the pruning power of the minimum support constraint. Furthermore, to efficiently check if a rowset is closed, we develop a method called the trace-based method. Based on these methods, an algorithm called TD-Close is designed for mining a complete set of frequent closed patterns. To enhance its performance further, we improve it by using new pruning strategies and new data structures that lead to a new algorithm TTD-Close. Our performance study shows that the top-down strategy is effective in cutting down search space and saving memory space, while the trace-based method facilitates the closeness-checking. As a result, the algorithm TTD-Close outperforms the bottom-up search algorithms such as Carpenter and FPclose in most cases. It also runs faster than TD-Close.     

Breaking symmetries in graph search with canonizing sets

There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to 10 vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.     

Issues in the performance measurement of constraint-satisfaction techniques

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate.Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.     

Constrained relative least general generalization for Inducing Constraint Logic Programs

Relative least general generalization proposed by Plotkin, is widely used for generalizing first-order clauses in Inductive Logic Programming, and this paper describes an extension of Plotkin’s work to allow various computation domains: Herbrand Universe, sets, numerical data, ect. The ?-subsumption in Plotkin’s framework is replaced by a more general constraint-based subsumption. Since this replacement is analogous to that of unification by constraint solving in Constraint Logic Programming, the resultant method can be viewed as a Constraint Logic Programming version of relative least general generalization. Constraint-based subsumption, however, leads to a search on an intractably large hypothesis space. We therefore providemeta-level constraints that are used as semantic bias on the hypothesis language. The constraintsfunctional dependency andmonotonicity are introduced by analyzing clausal relationships. Finally, the advantage of the proposed method is demonstrated through a simple layout problem, where geometric constraints used in space planning tasks are produced automatically.     

Feedback controlled particle swarm optimization and its application in time-series prediction

Particle swarm optimization (PSO) algorithm is an algorithmic technique for optimization by solving a wide range of optimization problems. This paper presents a new approach of extending PSO to solve optimization problems by using the feedback control mechanism (FCPSO). The proposed FCPSO consists of two major steps. First, by evaluating the fitness value of each particle, a simple particle evolutionary fitness function is designed to control parameters involving acceleration coefficient, refreshing gap, learning probabilities and number of the potential exemplars automatically. By such a simple particle evolutionary fitness function, each particle has its own search parameters in a search environment. Secondly, a local learning method using a competitive penalized method is developed to refine the solution. The FCPSO has been comprehensively evaluated on 18 unimodal, multimodal and composite benchmark functions with or without rotation. Compared with various state-of-the-art algorithms, including traditional PSO algorithms and representative variants of PSO algorithms, the performance of FCPSO is promising. The effects of parameter adaptation, parameter sensitivity and local search method are studied. Lastly, the proposed FCPSO is applied to constructing a radial basis neural network, together with the K-means method for time-series prediction.     

Reasoning from last conflict(s) in constraint programming

Constraint programming is a popular paradigm to deal with combinatorial problems in artificial intelligence. Backtracking algorithms, applied to constraint networks, are commonly used but suffer from thrashing, i.e. the fact of repeatedly exploring similar subtrees during search. An extensive literature has been devoted to prevent thrashing, often classified into look-ahead (constraint propagation and search heuristics) and look-back (intelligent backtracking and learning) approaches. In this paper, we present an original look-ahead approach that allows to guide backtrack search toward sources of conflicts and, as a side effect, to obtain a behavior similar to a backjumping technique. The principle is the following: after each conflict, the last assigned variable is selected in priority, so long as the constraint network cannot be made consistent. This allows us to find, following the current partial instantiation from the leaf to the root of the search tree, the culprit decision that prevents the last variable from being assigned. This way of reasoning can easily be grafted to many variations of backtracking algorithms and represents an original mechanism to reduce thrashing. Moreover, we show that this approach can be generalized so as to collect a (small) set of incompatible variables that are together responsible for the last conflict. Experiments over a wide range of benchmarks demonstrate the effectiveness of this approach in both constraint satisfaction and automated artificial intelligence planning.     

Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme

One of the most important issues in developing an evolutionary optimization algorithm is the proper handling of any constraints on the problem. One must balance the objective function against the degree of constraint violation in such a way that neither is dominant. Common approaches to strike this balance include implementing a penalty function and the more recent stochastic ranking method, but these methods require an extra tuning parameter which must be chosen by the user. The present paper demonstrates that a proper balance can be achieved using an addition of ranking method. Through the ranking of the individuals with respect to the objective function and constraint violation independently, we convert these two properties into numerical values of the same order of magnitude. This removes the requirement of a user-specified penalty coefficient or any other tuning parameters. Direct addition of the ranking terms is then performed to integrate all information into a single decision variable. This approach is incorporated into a (μ, λ) evolution strategy and tested on thirteen benchmark problems, one engineering design problem, and five difficult problems with a high dimensionality or many constraints. The performance of the proposed strategy is similar to that of the stochastic ranking method when dealing with inequality constraints, but it has a much simpler ranking procedure and does not require any tuning parameters. A percentage-based tolerance value adjustment scheme is also proposed to enable feasible search when dealing with equality constraints.     

A backtracking search tool for constructing combinatorial test suites

Combinatorial testing is an important testing method. It requires the test cases to cover various combinations of parameters of the system under test. The test generation problem for combinatorial testing can be modeled as constructing a matrix which has certain properties. This paper first discusses two combinatorial testing criteria: covering array and orthogonal array, and then proposes a backtracking search algorithm to construct matrices satisfying them. Several search heuristics and symmetry breaking techniques are used to reduce the search time. This paper also introduces some techniques to generate large covering array instances from smaller ones. All the techniques have been implemented in a tool called EXACT (EXhaustive seArch of Combinatorial Test suites). A new optimal covering array is found by this tool.     

Exploiting subproblem dominance in constraint programming

Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit subproblem dominance, which arises when different partial assignments lead to subproblems that dominate (or are dominated by) other subproblems. Subproblem dominance is exploited by caching subproblems that have already been explored by the search, using keys that characterise the subproblems, and failing the search when the current subproblem is dominated by a subproblem already in the cache. In this paper we show how we can automatically and efficiently define keys for arbitrary constraint problems using constraint projection. We show how, for search problems where subproblem dominance arises, a constraint programming solver with this capability can solve these problems orders of magnitude faster than solvers without caching. The system is fully automatic, i.e., subproblem dominance is detected and exploited without any effort from the problem modeller.