National and Kapodistrian University of Athens
Constraint programming: algorithms and systems
Abstract
dc:descriptionConstraint Programming aims at the easy declaration and fast resolution of Constraint Satisfaction Problems (CSPs) like course scheduling, radio link frequency assignment, etc. To solve the problems, Constraint Programming is based on search methods and constraint propagation. This dissertation contributes on both. Specifically: (i) We develop novel search methods that are based on new heuristics. These new heuristics implement the gradual randomization of deterministic heuristics. We create hybrid heuristics that exploit the advantages of both deterministic and random heuristics. (ii) We demonstrate how the MapReduce framework can be used for speeding up and distributing the search of a CSP solution to all the available solvers-workers. (iii) We highlight the advantages of relaxed constraint propagation levels like bounds consistency in comparison to higher levels like arc consistency. We propose new relaxed constraint propagation levels, and we compare their performance to higher propagation levels, both in theory and practice. We answer the question about when it is worth to employ relaxed constraint propagation levels. Our contributions were tested using mostly CSPs that occur in the real world and a wide range of CSPs included in official Constraint Programming solvers competitions. We used Naxos Solver as a practical open-source Constraint Programming solver to conduct our experiments.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Pothitos, Nikolaos
- Ποθητός, Νικόλαος
Subjects
dc:subject × 19- Αναζήτηση
- Ευρετικοί κανόνες
- Τυχαιοποίηση
- MapReduce
- Διάδοση περιορισμών
- Συνέπεια ορίων
- Διατήρηση συνέπειας ακμών
- Search
- Heuristics
- Randomization
- Constraint propagation
- Bounds consistency
- Maintaining arc consistency
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Τεχνητή νοημοσύνη
- Computer and Information Sciences
- Natural Sciences
- Artificial Intelligence
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/52375