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.     

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.     

Local and global symmetry breaking in itemset mining

The concept of symmetry has been extensively studied in the field of constraint programming and in the propositional satisfiability. Several methods for detection and removal of these symmetries have been developed, and their use in known solvers of these domains improved dramatically their effectiveness on a big variety of problems considered difficult to solve. The concept of symmetry may be exported to other areas where some structures can be exploited effectively. Particularly, in the area of data mining where some tasks can be expressed as constraints or logical formulas. We are interested here, by the detection and elimination of local and global symmetries in the item-set mining problem. Recent works have provided effective encodings as Boolean constraints for these data mining tasks and some idea on symmetry elimination in this area begin to appear, but still few and the techniques presented are often on global symmetry that is detected and eliminated statically in a preprocessing phase. In this work we study the notion of local symmetry and compare it to global symmetry for the itemset mining problem. We show how local symmetries of the boolean encoding can be detected dynamically and give some properties that allow to eliminate theses symmetries in SAT-based itemset mining solvers in order to enhance their efficiency.     

对称在破裂孤立子方程中的应用

首先对带有积分项的破裂孤立子方程（breaking soliton equation）进行变换,然后利用待定系数法求出它的对称,通过验证知道原方程的李群能构成李代数,再利用优化系统对原方程进行约化,求出了原方程的一些新解。     

Distributing identity [symmetry breaking distributed accessprotocols]

In the next few years, computational, sensory, and communication capabilities will diffuse out of their present home in beige boxes on desktops and into everyday objects such as furniture, clothing, and other non-technological objects. As the cost of electronics continues to drop, the number of activated, networked devices will grow rapidly. Each device sharing a particular multiaccess channel will need a unique identifier for that channel. Present communication protocols such as Ethernet specify that the manufacturers must coordinate with one another in order to avoid assigning the same ID twice. The article explores methods by which the devices could coordinate with one another to manage ID assignment dynamically and automatically. In particular, the article is an investigation of distributed protocols that utilize physical sources of symmetry breaking to enable a network of initially identical units to acquire the unique identities required for point-to-point communication over a shared resource such as a bus or common RF band. It presents several protocols, compares their resource use (time, random bits, space, communication), and notes a trade-off among these measures of algorithm complexity     

Lifting symmetry breaking constraints with inductive logic programming

Machine Learning - Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. Most of the existing approaches are instance-specific and focus on the...     

Phase transitions and symmetry breaking in genetic algorithms with crossover

In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In doing so, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm.     

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.     

Analysis of emergent symmetry breaking in collective decision making

We investigate a simulated multi-agent system (MAS) that collectively decides to aggregate at an area of high utility. The agents’ control algorithm is based on random agent–agent encounters and is inspired by the aggregation behavior of honeybees. In this article, we define symmetry breaking, several symmetry breaking measures, and report the phenomenon of emergent symmetry breaking within our observed system. The ability of the MAS to successfully break the symmetry depends significantly on a local-neighborhood-based threshold of the agents’ control algorithm that determines at which number of neighbors the agents stop. This dependency is analyzed and two macroscopic features are determined that significantly influence the symmetry breaking behavior. In addition, we investigate the connection between the ability of the MAS to break symmetries and the ability to stay flexible in a dynamic environment.     

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

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

Efficient symmetry breaking formulations for the job grouping problem

The job grouping problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. Traditionally, a formulation has been used that assigns jobs to machines. However, such a formulation contains a lot of symmetry since the machines are identical and they can be permuted in any feasible solution. We propose a new formulation for this problem, based on the asymmetric representatives formulation (ARF) idea. This formulation eliminates the symmetry between the identical machines. We further propose various symmetry breaking constraints, including variable reduction and lexicographic ordering constraints, which can be added to the traditional formulation. These formulations are tested on a data set from the literature and newly generated data sets using a state-of-the-art commercial solver, which includes symmetry breaking features.     

Spontaneous symmetry breaking for long-wave gravitons in the early Universe

It is shown that nonlinear terms in the equations for gravitons in the background of curved space-time of the expanding Universe can solve the problem of the negative effective mass squared, formally arising in the linear approximation for gravitons. Similarly to the well-known spontaneous symmetry breaking in the Goldstone model, one must take another vacuum, so that a nonzero vacuum expectation value of the quantized graviton field leads to a change in the graviton spectrum. There appear two graviton fields, one with positive mass, another with zero mass. The energy density and the density of particles created by gravitation of the expanding Universe are calculated for some special cases of the scale factor. Numerical results are obtained for the case of a dust universe.     

Static realization of dynamic precompensators

The problem of static realization of dynamic precompensators on a controllable pair (A,B) is considered. Necessary and sufficient conditions for the solution of this problem in the general case are given. These conditions are constructive, and they apply not only to invertible precompensators but also to those which are only left invertible     

Glass transition and the replica symmetry breaking in vortex matter: MC study

We investigate effects of disorder and thermal fluctuations on the Abrikosov state of type II superconductors applying the Monte Carlo method to Ginzburg–Landau theory to confirm earlier replica calculation. The vortex phase diagram has two transition lines, the melting line and the vortex glass transition lines in both crystalline and homogeneous states. The glass line is always a continuous transition, while the melting line is the first order.     

Computing the Ramsey number R(4,3,3) using abstraction and symmetry breaking

The number R(4, 3, 3) is often presented as the unknown Ramsey number with the best chances of being found “soon”. Yet, its precise value has remained unknown for almost 50 years. This paper presents a methodology based on abstraction and symmetry breaking that applies to solve hard graph edge-coloring problems. The utility of this methodology is demonstrated by using it to compute the value R(4, 3, 3) = 30. Along the way it is required to first compute the previously unknown set \(\mathcal {R}(3,3,3;13)\) consisting of 78,892 Ramsey colorings.     

Static and dynamic adaptations for service-based systems

Context

In service-oriented computing (SOC), service providers publish reusable services, and service consumers subscribe them. However, there exist potential problems in reusing services. Mismatch is a problem that occurs when a candidate service does not fully match to the feature expected. Fault is a problem that occurs when an invocation of services results in some abnormality at runtime. Without remedying mismatch problems, services would not be reusable. Without remedying fault problems, service invocations at runtime would result in failures. Static and dynamic adaptations are practical approaches to remedying the problems.

Objective

Our objective is to define a comprehensive framework which includes a design of service adaptation framework (SAF), and design of static and dynamic adapters.

Method

We design the SAF which governs dynamic adaptations, and define a service life-cycle with adaptation-related activities. Based on causal–effect relationships among mismatch, fault, cause, and adapter, we derive mismatches and faults, from which their relevant causes are identified. For the causes, we define six static adapters and five dynamic adapters. We specify instructions for designing static adapters, and provide step-wise algorithms for designing dynamic adapters based on enterprise service bus (ESB). And, we show a proof-of-concept (POC) of implementation to show applicability of the methods.

Results

The paper presents service life-cycle with adaptation-related activities, SAF design, and design of static and dynamic adapters.

Conclusion

Mismatch and fault problems in utilizing services present threats to high reusability of services. Static adaptations can remedy mismatch problems, and dynamic adaptations can remedy fault problems. In this paper, we presented technical insights of service adaption, SAF design, and definitions of static and dynamic adapters. By utilizing the proposed SAF and service adapters, reusability of services can be greatly enhanced.     

Static and dynamic analysis of stiffened plates

In this paper a method for the static and dynamic analysis of eccentrically stiffened annular sector plates is presented. The plate is clamped on all the edges. The integral equation technique is adopted for the solution. In the static analysis the deflection and stresses at centre and the stresses at the edges are obtained and they are presented graphically. The results are compared for particular cases with those of other investigators who have used different analytical methods. The natural frequencies of stiffened clamped plates are also obtained for plates with different sector angles.     

Improved solutions for the freight consolidation and containerization problem using aggregation and symmetry breaking

We consider the freight consolidation and containerization problem, which consists of loading items into containers and then shipping these containers to different warehouses from where they are delivered to their final destinations. We show through computational experiments that very good solutions can be obtained by heuristically aggregating the items and then using MIP approaches to deal with the aggregated problem. We have been able to find a solution as good as the best known in the literature for 100% of the instances with small items, encountering strictly better solutions for 40.6% of them. Our approach found solutions as good as the best known in the literature for 88.9% of the instances with large items, obtaining strictly better in 59.4% of the cases.     

Static condensation in modal-based structural optimization

The modal-based structural optimization method with static aeroelastic and stress constraints is expanded to include Guyan's static condensation option. Unlike in the regular discrete-coordinate approach, where the condensation is just a numerical option with no effect on the static results, it does affect the modal-based results through its effects on the modes taken into account. It is shown that in many cases the condensation is not effective and may increase the modal-based errors. However, when applied to structural parts which are not subject to redesign, the condensation yields accurate results and causes a significant reduction in computation time. This facilitates extremely efficient on-line design sessions in which repeated optimization studies are performed with a given baseline structure.     

Static and dynamic aspects of goal-oriented concurrency control

A new correctness criterion for schedules of update transactions is proposed, which captures users' intended changes to the database. This is motivated by the observation that traditional serializability may lead to anomalies by not taking into account semantics related to such intended changes. The alternate criterion —goal-correctness — is orthogonal to serializability, and is based on realizing goals associated with each transaction. The problems involved in goal-oriented concurrency control are first identified in a general framework. The analysis suggests that this approach is practical only for restricted transaction languages where goals can be inferred and manipulated efficiently. One such language is then considered, capturing a class of updates of practical interest. For this language, it is shown that goal-oriented concurrency control is tractable and compares favorably to serializability with respect to complexity: testing goal-correctness takes polynomial time, while testing serializability is NP-complete. The set of schedules which are correct with respect to the two criteria are incomparable. Thus, goal-correctness may allow increased concurrency. The results highlight the feasibility and advantages of goal-oriented concurrency control in restricted frameworks. The paper also discusses the dynamic aspects of goal-oriented concurrency control; in particular, an optimistic approach to the dynamic generation of goal-correct schedules is presented.An extended abstract of this paper appeared in the Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems (MFDBS), LNCS 364 (Springer, 1989) pp. 398–414.This author was supported in part by the National Science Foundation, under Grant Number IRI-8816078.