@phdthesis{Loeffler2022, author = {L{\"o}ffler, Sven}, title = {Optimierung und Regularisierung von Constraint Satisfaction-Problemen (CSPs)}, doi = {10.26127/BTUOpen-6149}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61490}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {Mit Hilfe der Constraint-Programmierung k{\"o}nnen komplexe, h{\"a}ufig NP-vollst{\"a}ndige Probleme, wie zum Beispiel Graphf{\"a}rbungs-, Optimierungs-, Konfigurations- sowie Schichtplanungs-, Raum- und Zeitplanungsprobleme modelliert und gel{\"o}st werden. Im Vordergrund der Constraint-Programmierung steht dabei die deklarative Modellierung, also eine Beschreibung des eigentlichen Problems und nicht dessen L{\"o}sungsvorgangs. W{\"a}hrend es Aufgabe des Entwicklers ist, das Problem zu modellieren, wird die L{\"o}sung einem separat implementierten Solver (L{\"o}ser) {\"u}berlassen. Im Idealfall l{\"o}st dieser Solver das Problem, unabh{\"a}ngig von der konkreten Modellierung, immer schnellstm{\"o}glich. In der Praxis kann von diesem Idealfall in der Regel nicht ausgegangen werden und somit hat die Art und Weise der Modellierung ein und desselben Problems und dessen Remodellierung teilweise einen erheblichen Einfluss auf die L{\"o}sungsgeschwindigkeit. Bisher bestehende Remodellierungsverfahren transformieren entweder Constraint-Probleme im Ganzen (zum Beispiel beim Umwandeln in SAT- oder bin{\"a}re Constraint-Probleme) oder erfordern eine pr{\"a}zise Angabe und Steuerung seitens des Nutzers der Constraint-Programmierung (zum Beispiel bei der Tabularisierung). W{\"a}hrend die erste Variante in der Regel nur bei sehr speziellen Problemen zu einer Beschleunigung des L{\"o}sungsvorganges f{\"u}hrt, ben{\"o}tigt die zweite Variante vom Constraint-Modellierer zus{\"a}tzliches Expertenwissen {\"u}ber das L{\"o}sungsverfahren des verwendeten Solvers. Die bisherigen Verfahren erlauben somit keine (voll)-automatisierte Transformation von Constraint-Problemen, bei der Transformationen nur durchgef{\"u}hrt werden, wenn diese auch zu einer Beschleunigung f{\"u}hren. F{\"u}r das dieser Arbeit {\"u}bergeordnete Ziel der automatisierten Optimierung von Constraint-Problemen mittels Remodellierung, ohne dass daf{\"u}r zus{\"a}tzliches Expertenwissen notwendig ist, werden ausreichend viele verschiedene, gute und gut untersuchte Remodellierungen ben{\"o}tigt. In dieser Arbeit werden daher sowohl bestehende Verfahren f{\"u}r die Transformation von Constraint-Problemen weiterentwickelt, als auch v{\"o}llig neue entworfen und deren Korrektheit nachgewiesen. Die in dieser Arbeit entwickelten Transformationen werden bez{\"u}glich ihrer beschleunigenden Wirkung auf Constraint-Probleme untersucht. Anhand von generierten und von realen Praxisbeispielen wird die Wirksamkeit der Transformationen evaluiert und es werden Schlussfolgerungen dar{\"u}ber gezogen, wann welche Substituierungen besonders vielversprechend sind.}, subject = {Constraint Satisfaction-Problem; Constraint satisfaction problem; Optimierung; Optimization; Regularisierung; Regularization; CSP; SAT; Constraint-Erf{\"u}llung; Regularisierung; Optimierung}, language = {de} }