• search hit 3 of 9
Back to Result List

Parallel constraint solving for combinatorial problems

Paralleles Constraint Solving für kombinatorische Probleme

  • With parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problemWith parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problem with predefined venues and the talent scheduling problem. Our proposed constraint models outperformed the existing models on the same instances, and the EPS approach could always attain better feasible solutions in terms of the optimal objective value by using more parallel processors. To explore the use of massively parallel processing, we proposed the parallel stochastic portfolio search, which is a simple and non-intrusive way to parallelize different incarnations of a sequential solver. When comparing the existing portfolio to our portfolio approach by solving the same constraint satisfaction problems using the same constraint models, our technique could solve harder and larger instances. The successes of our new parallel approaches are attributed to early diversity; i.e., some diversity early in the search introduced by parallelism can offset early mistakes caused by weak heuristic choices. Unlike the other techniques (e.g., limited discrepancy search) used to overcome early mistakes, the studied two parallel constraint solving approaches not only can explore more nodes simultaneously but also does not sacrifice the guarantee of completeness. We also presented a hypertree decomposition method that builds a degenerate decomposition tree for a given constraint network, in which each node of the decomposition tree possesses and executes a subset of constraints of the given constraint network. The usefulness of our proposed parallel techniquedepends on whether we can find an efficient way to join the results of each node.show moreshow less
  • Da Parallelität zum Standard im Computerdesign geworden ist, ist die Erforschung paralleler Constraint-Solving-Techniken von entscheidender Bedeutung, um die Leistung des Constraint-Solving zu verbessern. In dieser Dissertation wurde die Literatur zur Ausnutzung der Parallelität bei der Lösung von Nebenbedingungen durchgesehen, um einen Einblick in die Gründe für die verschiedenen Arten von parallelen Lösungsansätzen für Nebenbedingungen zu erhalten. Auf dieser Grundlage haben wir die Effektivität des parallelen Lösens von Nebenbedingungen analysiert, wobei der Schwerpunkt auf der Erlangung einer ersten Lösung beim Lösen rechenintensiver kombinatorischer Probleme lag. Wir haben gezeigt, dass eine gut konzipierte Suchraumaufteilungsmethode und ein Constraint-Programmiermodell die peinlich parallele Suche (EPS) in die Lage versetzen kann, einige offene Instanzen des sozialen Golferproblems zu lösen, die von einem sequentiellen Algorithmus nicht gelöst werden konnten. Wir beobachteten auch superlineare Beschleunigungen beim Lösen dieserDa Parallelität zum Standard im Computerdesign geworden ist, ist die Erforschung paralleler Constraint-Solving-Techniken von entscheidender Bedeutung, um die Leistung des Constraint-Solving zu verbessern. In dieser Dissertation wurde die Literatur zur Ausnutzung der Parallelität bei der Lösung von Nebenbedingungen durchgesehen, um einen Einblick in die Gründe für die verschiedenen Arten von parallelen Lösungsansätzen für Nebenbedingungen zu erhalten. Auf dieser Grundlage haben wir die Effektivität des parallelen Lösens von Nebenbedingungen analysiert, wobei der Schwerpunkt auf der Erlangung einer ersten Lösung beim Lösen rechenintensiver kombinatorischer Probleme lag. Wir haben gezeigt, dass eine gut konzipierte Suchraumaufteilungsmethode und ein Constraint-Programmiermodell die peinlich parallele Suche (EPS) in die Lage versetzen kann, einige offene Instanzen des sozialen Golferproblems zu lösen, die von einem sequentiellen Algorithmus nicht gelöst werden konnten. Wir beobachteten auch superlineare Beschleunigungen beim Lösen dieser Instanzen, was unsere theoretische Analyse bestätigt. Außerdem untersuchten wir zwei praktische Constraint-Optimierungsprobleme, darunter das Traveling-Turnier-Problem mit vordefinierten Austragungsorten und das Talentplanungsproblem. Die von uns vorgeschlagenen Constraint-Modelle übertrafen die bestehenden Modelle bei denselben Instanzen, und der EPS-Ansatz konnte durch die Verwendung von mehr parallelen Prozessoren immer bessere machbare Lösungen in Bezug auf den optimalen Zielwert erzielen. Um die Verwendung von massiv paralleler Verarbeitung zu erforschen, haben wir die parallele stochastische Portfoliosuche vorgeschlagen, die eine einfache und nicht-intrusive Methode zur Parallelisierung verschiedener Inkarnationen eines sequentiellen Solvers ist. Beim Vergleich des existierenden Portfolios mit unserem Portfolio-Ansatz durch Lösen der gleichen Constraint-Satisfaction-Probleme unter Verwendung der gleichen Constraint-Modelle konnte unsere Technik schwierigere und größere Instanzen lösen. Die Erfolge unserer neuen parallelen Ansätze werden auf die frühe Diversität zurückgeführt, d. h. eine gewisse Diversität zu Beginn der Suche, die durch die Parallelität eingeführt wird, kann frühe Fehler ausgleichen, die durch schwache heuristische Entscheidungen verursacht werden. Im Gegensatz zu anderen Techniken (z. B. begrenzte Diskrepanzsuche), die zur Überwindung früher Fehler verwendet werden, können die beiden untersuchten parallelen Ansätze zum Lösen von Beschränkungen nicht nur mehr Knoten gleichzeitig untersuchen, sondern opfern auch nicht die Garantie der Vollständigkeit. Wir haben auch eine Hypertree-Dekompositionsmethode vorgestellt, die einen degenerierten Dekompositionsbaum für ein gegebenes Constraint-Netzwerk aufbaut, bei dem jeder Knoten des Dekompositionsbaums eine Teilmenge von Constraints des gegebenen Constraint-Netzwerks besitzt und ausführt. Die Nützlichkeit der von uns vorgeschlagenen parallelen Technik hängt davon ab, ob wir einen effizienten Weg finden können, die Ergebnisse der einzelnen Knoten zu verbinden.show moreshow less

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Ke LiuORCiD
URN:urn:nbn:de:kobv:co1-opus4-53999
DOI:https://doi.org/10.26127/BTUOpen-5399
Referee / Advisor:Prof. Dr. rer. nat. habil. Petra Hofstedt, Prof. Dr. Salvador Abreu
Document Type:Doctoral thesis
Language:English
Year of Completion:2021
Date of final exam:2021/01/20
Release Date:2021/02/11
Tag:Constraint-Programmierung; Lösen von Zwangsbedingungen; Paralleles Rechnen; SGP
Constraint programing; Parallel computing; Parallel constraint solving
GND Keyword:Constraint-Programmierung; Parallelverarbeitung
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Programmiersprachen und Compilerbau
Other Notes:Ungültiges Dokument. Ersetzt durch: Korrigiertes Dokument
Licence (German):Keine Lizenz vergeben. Es gilt das deutsche Urheberrecht.
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.