TU Darmstadt / ULB / tuprints

Breaking Weak Symmetries in Constraint Programming

Martin, Roland :
Breaking Weak Symmetries in Constraint Programming.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2007)

[img]
Preview
PDF
Diss_WeakSym_RM.pdf
Available under Simple publication rights for ULB.

Download (2629Kb) | Preview
Item Type: Ph.D. Thesis
Title: Breaking Weak Symmetries in Constraint Programming
Language: English
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.

Alternative Abstract:
Alternative AbstractLanguage
Viele Probleme aus Industrie und Wirtschaft sind kombinatorische Probleme mit einer sehr hohen Komplexität. D. h. bisher ist kein Algorithmus bekannt, welcher diese Art von Problemen (oder auch nur eines davon) effizient löst. Constraint Programming bietet Techniken, welche es ermöglichen schwere kombinatorische Probleme beweisbar zu lösen, ohne tatsächlich jede Lösungskombination explizit zu berechnen. Das Prinzip der Beweisbarkeit beruht auf der Tatsache, daß mögliche Lösungskombinationen von der Suche ausgeschlossen werden, falls sie nicht zulässig sind. Dies geschieht über Inferenz-Verfahren, welche unzulässige Variablenbelegungen erkennen, noch bevor sie instantiiert werden. Dadurch können frühzeitig ganze Teilbereiche des Lösungsraums von der Suche ausgeschlossen werden, so daß sich die Anzahl von tatsächlich zu berechnenden Lösungen drastisch verkleinert. Wenn alle diese verbliebenden Lösungenskombination berechnet sind, ist das Problem exhaustiv betrachtet und im Falle der Optimierung ist eine optimale Lösung gefunden. Im Falle eines Entscheidungsproblemes wurde entweder eine Lösung während des Suchprozesses gefunden oder durch die exhaustive Suche bewiesen, daß keine Lösung existiert. Symmetrien in Problemen bilden die kombinatorischen Möglichkeiten eines Problemes auf sich selbst ab. Symmetriebehandlung (auch Symmetriebrechung genannt) reduziert das Problem auf seinen kombinatorischen Kern. Besteht ein Problem aus der Belegung von n Variablen und sind diese Variablen symmetrisch, dann existieren n! viele Permutationen für eine beliebige Lösung. Ein simples Beispiel ist eine Nebenbedingung der Form: x_1 + x_2 + x_3 = 6. Eine Lösung für diese Nebenbedingung ist z.B. x_1=1, x_2=2, x_3=3. Jede Permutation der Werte ist aber ebenso eine Lösung, weil (1+2+3=1+3+2=2+1+3=2+3+1=3+1+2=3+2+1=6). Es existieren also sechs Lösungen, welche genau die gleiche Lösung (nämlich die Werte 1,2,3 zu benuten) beschreiben. Symmetrien bilden eine mathematische Gruppe und daher kann die Gruppentheorie benutzt werden, um zu zeigen, daß das Auschließen von symmetrischen Lösungen eine korrekte Methode ist, den Lösungsraum zu verkleinern, ohne Information zu verlieren. In dieser Dissertation klassifizieren wir eine neue Art von Symmetrie, welche die Eigenschaft hat, daß sie nur auf einem Teilproblem P_1 des ursprünglichen Problems P symmetrisch ist. D. h. daß es Variablen und/oder Nebenbedingungen in P gibt, denen die Symmetriefunktion nicht genügt. Diese Symmetrie nennen wir schwache Symmetrie (weak symmetry). Schwache Symmetrien können nicht auf dem Problem P gebrochen werden, weil eine schwach symmetrische Variablenbelegung, welche dem Problem P_1 genügt (d.h. das Nebenbedingungssystem erfüllt) nicht automatisch auch P genügt. Insbesondere bedeutet dies, daß nicht alle schwach symmetrischen Equivalente einer Lösung, welche P_1 erfüllt zu den gleichen Lösungen für P führen. Symmetriebrechung von schwachen Symmetrien auf dem Problem P führt daher zu einem irreversiblen Verlust von Lösungen, so daß ein Problem nicht mehr beweisbar gelöstwerden kann. Wir führen in dieser Dissertation eine Technik ein, welche es uns erlaubt, schwache Symmetrien zu brechen, ohne Lösungen zu verlieren. Dazu führen wir zusätzliche Variablen ein, welche es erlauben, die durch die Symmetriebrechung augeschlossenen Lösungen während der Suche zu rekonstruieren. Dies ermöglicht es, Symmetriebrechung anzuwenden und damit den Lösungsraum zu verkleinern, ohne Lösungen zu verlieren. Es werden also nur solche Variablenbelegungen ausgeschlossen, welche tatsächlich keine neue Lösung liefern. Diese Technik ist unabhängig vom eingesetzten Solver und benötigt keinen zusätzlichen Programmcode, um angewandt zu werden. Dadurch ist unsere vorgestellte Technik nicht an eine bestimmte Software gebunden und steht jedem zur Verfügung, der sich mit Constraint Programming beschäftigt. Das Anwenden erfordert zudem kein Wissen in Gruppentheorie, sondern nur grundlegende Modellierungsfähigkeiten. Dies erweitert den Anwenderkreis weiterhin. Die meisten Probleme aus der Industrie und Wirtschaft bestehen aus mehreren Teilproblemen, welche nicht unabhängig voneinander gelöst werden können. Gerade diese Probleme beinhalten meist keine Symmetrien sondern nur schwache Symmetrien. Unsere Technik erlaubt es nun also neue Anwendungsfelder für Constraint Programming im allgemeinen und die Symmetriebrechung im speziellen zu erschließen.German
Uncontrolled Keywords: Constraint-Programming, Symmetriebrechung, Modellierung, schwache Symmetrie, Optimierung, Erfüllbarkeitsprobleme, Symmetrievariable
Alternative keywords:
Alternative keywordsLanguage
Constraint-Programming, Symmetriebrechung, Modellierung, schwache Symmetrie, Optimierung, Erfüllbarkeitsprobleme, SymmetrievariableGerman
Constraint Programming, Symmetry Breaking, Weak Symmetry, Modelling, Modeling, Optimisation, Optimization, Constraint Satisfaction, Symmetry VariableEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:53
Official URL: http://elib.tu-darmstadt.de/diss/000863
URN: urn:nbn:de:tuda-tuprints-8636
License: Simple publication rights for ULB
Referees: Sellmann, Prof. Dr. Meinolf
Advisors: Weihe, Prof. Dr. Karsten
Refereed: 11 May 2007
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/863
Export:

Actions (login required)

View Item View Item