Martin, Roland (2007)
Breaking Weak Symmetries in Constraint Programming.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Constraint programming (CP) is a powerful solving paradigm that is based on inference and search control algorithms and suitable for arbitrary/various NP-hard combinatorial problems beyond linearity. The flexibility of constraints - the working machines of a CP solver - allow a wide range of problems to be solved by constraint programming solvers. Constraint propagation and search control are to two main concepts that make CP an efficient solving strategy. The former identifies infeasible regions of the search space and prunes them. The latter allows to state search heuristics that guide the search in more promising regions of the search space. A problem is passed to a constraint solver by a model using variables and constraints. The flexibility of modelling a problem for a CP solver allows rapid prototyping and solving whereas problem-tailored algorithms need a long development time. Small changes in the problem description can be compensated by just altering the model while problem-tailored algorithms may be not applicable to the new situation anymore. This makes constraint programming very robust in terms of modelling. Another very powerful approach in constraint programming is symmetry breaking. A symmetry in constraint programming can be seen as a function mapping several solutions to each other. A symmetry preserves the feasibility state of a solution. Therefore, solutions that are symmetric are either all feasible or all infeasible and build a solution class. Symmetry breaking reduces the problem to its combinatorial core by excluding all but one symmetric solution of each solution class. The search space is significantly reduced by excluding equivalent solutions from the search such that only unique regions of the search space are investigated during the search. A condition for symmetry breaking to be sound is that no unique solution is excluded in the process of symmetry breaking. All symmetry breaking methods are based upon this necessary criteria. There are several symmetry breaking methods proposed during the last years and the success of these methods was proved in several publications on conferences and workshops. In this thesis we investigate a kind of symmetry we call weak symmetry. Weak symmetries have the special property that the weak symmetric equivalents are only equivalent for a subset of the variables and constraints of a problem, i.e. some variables and constraints are not respected by the symmetry. Solutions that are weak symmetric are only full symmetric with respect to the subset of the variables and constraints of the problem. This means that in the context of the full problem weak symmetric solutions can have different feasibility states. Excluding all but one solution, as it is done by symmetry breaking, does exclude solutions that cannot be retrieved afterwards. Therefore, a weak symmetry cannot be broken by standard symmetry methods without losing solutions. Weak symmetries are interesting from an academical view on how to break them in order to again reduce the problem to its combinatorial core. But moreover, although only recently discovered weak symmetries have already a large application range. Weak symmetries arise in classical areas as optimisation and satisfaction as well as in real-world scenarios, distributed constraint satisfaction programmes soft constraints, planning, scheduling, and model checking. In the first field - real-world problems - weak symmetries often arise by an objective function or just by the fact that the problem investigated consists of several interlinked problems which cannot be solved individually without conflicting with the other subproblems. In the former three fields - real-world problems, soft constraints and distributed constraint satisfaction programmes - often there are more weak symmetries than standard symmetries. With weak symmetry breaking new problem classes can be handled more efficiently by constraint programming. Therefore, weak symmetry breaking introduces a large potential of improvement for symmetry breaking in particular and constraint programming in general. In this thesis we classify weak symmetries and introduce an approach to weak symmetry breaking that is based on pure modelling. The advantages of this approach are: Universality: Every solver uses a modelling language to state problems that are passed to the solver. Our approach does not need additional implementations so we are not limited to a specific solver. Ease of use: A person familiar with modelling can adept the approach easily and is capable of remodelling a problem to break weak symmetries. Although modelling needs some expertise the principles of modelling weak symmetries are very easy to understand such that even inexperienced constraint programmer can use the technique immediately. No background knowledge required: Symmetries are based on groups and therefore the theory of symmetries and symmetry breaking is group theory. It is possible to use weak symmetry breaking without specific knowledge of group theory. Readiness: Since no extra code has to be written, incorporated or adjusted, our approach can be used instantly. Existing models can be easily upgraded with weak symmetry breaking with just a few changes to the constraints. Interoperability: When a model is revised, the weak symmetry can be handled using standard symmetry breaking methods such that the approach also profits from research in this field. Any symmetry breaking method can be used once the model is revised in the way we propose. Concurrent Symmetry Breaking: Problems may contain standard and weak symmetries. Both can be handled concurrently since weak symmetry breaking actually transforms a weak symmetry into a standard symmetry from a certain viewpoint. Robustness: Since no method specific code has to be added to the existing solver, the chance of producing errors is minimal and reduced to the validity of the model. But there is no problem with memory management, exception handling, etc. Openness to Refinement: The basic approach can be extended in several ways to suit different applications. For example, it is easy to adopt the approach for partial symmetries. Although based on modelling, it is also possible to extend the approach by incorporating code to the constraint solver. This way the approach can be adopted to various applications and scenarios in order to maximise efficiency. Our approach is based on introducing new variables to a model called SymVars. The set of SymVars represent symmetric equivalents of solutions to a symmetric subproblem P_1 of the regarded constraint satisfaction problem P, whereby P is not symmetric. The search space of the SymVars represents the whole equivalence class of a solution that is weakly symmetric on P. Since all symmetric equivalents of a solution to P_1 are reflected by the SymVars, it is sufficient to find just one solution of each equivalence class in P_1. That is exactly what symmetry breaking does. Therefore, by introducing SymVars, we are able to break the weak symmetry on the problem by standard symmetry breaking methods. If the search encounters a feasible variable assignment (with respect to the symmetric part P_1 of the problem) its symmetric equivalents are investigated to see whether one of them also satisfies the asymmetric part of the problem. If so, a solution is found and if not a different variable assignment is sought that satisfies the constraints of P_1. For this variable assignment again the symmetric equivalents are investigated and so on. Depending on the problem, we do not have to search the whole equivalence class of a solution. Infeasibility can be determined for partial SymVar instantiations such that backtracking can be performed excluding parts of the search space. It is also possible to state a variable and value ordering on the subproblem of instantiating the SymVars which can help to investigate the equivalence class faster. We also demonstrate some techniques to speed up our approach. Some of them are based on modelling like stating conditional constraints to annihilate search on the stabiliser of a variable assignment. Other techniques require writing code and incorporate this in the solver. One of these techniques is based on exploiting special behaviour for a class of problems. In this class, an objective function evaluates the each solution and the function is separable. This means that certain parts of a solution contribute a specific amount to the objective value and this amount is independent from the rest of the solution. In these problems, we can impose a domination criteria on partial solutions such that we can (by storing partial information) prune large parts of the search space in addition to the savings provided by weak symmetry breaking.

Frage zum Eintrag

Redaktionelle Details anzeigen