Constraint programming: algorithms and systems

Abstract

Constraint 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.

Ο Προγραμματισμός με Περιορισμούς (Constraint Programming) αποσκοπεί στην εύκολη διατύπωση και γρήγορη επίλυση των λεγόμενων Προβλημάτων Ικανοποίησης Περιορισμών (Constraint Satisfaction Problems – CSPs) όπως η κατάστρωση ωρολογίων προγραμμάτων, η ανάθεση συχνοτήτων σε ραδιοφωνικούς σταθμούς χωρίς παρεμβολές μεταξύ τους κ.ά. Για την επίλυση των προβλημάτων, ο Προγραμματισμός με Περιορισμούς βασίζεται στις μεθόδους αναζήτησης (search methods) και στη διάδοση περιορισμών (constraint propagation). Η διατριβή αυτή συνεισφέρει και στους δύο αυτούς πυλώνες. Πιο συγκεκριμένα: (i) Αναπτύσσουμε καινούργιες μεθόδους αναζήτησης που βασίζονται σε καινοτόμους ευρετικούς κανόνες. Οι κανόνες αυτοί υλοποιούν τη βαθμιαία τυχαιοποίηση των ντετερμινιστικών ευρετικών κανόνων. Δημιουργούμε ένα υβρίδιο με στόχο την εκμετάλλευση των πλεονεκτημάτων τόσο των ντετερμινιστικών όσο και των τυχαίων ευρετικών κανόνων. (ii) Αξιοποιούμε το πλαίσιο MapReduce προκειμένου να επιταχύνουμε και να κατανείμουμε την αναζήτηση λύσης ενός Προβλήματος Ικανοποίησης Περιορισμών σε όλους τους επιλυτές-εργάτες που τυχαίνει να έχουμε στη διάθεσή μας. (iii) Αναδεικνύουμε τα πλεονεκτήματα των χαλαρών επιπέδων διάδοσης περιορισμών, όπως η συνέπεια ορίων (bounds consistency) έναντι υψηλότερων επιπέδων όπως η συνέπεια ακμών (arc consistency). Προτείνουμε καινούργιες μορφές χαλαρών επιπέδων διάδοσης περιορισμών και συγκρίνουμε την απόδοσή τους σε σχέση με τα υψηλότερα επίπεδα διάδοσης περιορισμών, τόσο θεωρητικά όσο και πρακτικά. Απαντάμε στην ερώτηση για το πότε συμφέρει να χρησιμοποιούμε χαλαρά επίπεδα διάδοσης περιορισμών. Οι συνεισφορές μας δοκιμάστηκαν ως επί το πλείστον σε Προβλήματα Ικανοποίησης Περιορισμών από τον πραγματικό κόσμο, αλλά και σε μια ευρύτερη γκάμα προβλημάτων που χρησιμοποιούνται σε επίσημους διαγωνισμούς επιλυτών Προγραμματισμού με Περιορισμούς. Ένας τέτοιος πρακτικός επιλυτής ανοικτού κώδικα είναι ο Naxos Solver που χρησιμοποιήσαμε ως το πεδίο εφαρμογής των πειραμάτων.