Constraint programming

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