Adaptive strategies for solving contraint satisfaction problems

Abstract

A major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP). In recent years adaptive approaches for solving CSPs have attracted the interest of many researchers. General speaking a strategy that uses the results of its own search experience to modify its subsequent behavior does adaptive search In this dissertation we explore adaptive strategies for backtracking search on various levels. First, we investigate adaptive search guiding heuristics for ordering variables in CSPs. These adaptive heuristics learn and use information from every node explored in the search tree whereas traditional static and dynamic heuristics only use information about the initial and current nodes. We then perform a wide empirical evaluation of the proposed variable ordering heuristics and compare them with the current state of the art variable ordering strategies. Concerning constraint propagation which is used as an inference mechanism in order to simplify a problem so as to make it easier to solve we explore adaptive strategies for ordering the different revisions performed when enforcing arc consistency algorithms. Next we propose adaptive branching heuristics for splitting the search tree. The application of these heuristics results in an adaptive branching scheme. Experiments with instantiations of the proposed generic heuristics confirm that search with adaptive branching outperforms search with a fixed branching scheme on a wide range of problem. Finally we propose a new a generic approach for branching where the variable’s domains are grouped into sets by using the scores assigned to values by a value ordering heuristic and a clustering algorithm from machine learning. In general this dissertation contributes to the design and implementation of adaptive and autonomous constraint solvers that have the ability to advantageously modify modelers decisions that typically in mainstream CP solvers are taken prior to search.

Μια σημαντική πρόκληση στον προγραμματισμό με Περιορισμούς είναι η ανάπτυξη αποτελεσματικών γενικών αλγορίθμων και τεχνικών για την επίλυση των Προβλημάτων Ικανοποίησης Περιορισμών (ΠΙΠ). Τα τελευταία χρόνια διάφορες προσαρμοστικές τεχνικές για την επίλυση των ΠΙΠ έχουν προσελκύσει το ενδιαφέρον πολλών ερευνητών. Γενικά μιλώντας μια στρατηγική που χρησιμοποιεί τα αποτελέσματα των δικών της εμπειριών για να τροποποιήσει μεταγενέστερα τη συμπεριφορά της ονομάζεται προσαρμοστική στρατηγική. Σε αυτή τη διατριβή ερευνούμε προσαρμοστικές στρατηγικές για την αναζήτηση με χρήση αλγορίθμων οπισθοδρόμησης σε διάφορα επίπεδα. Αρχικά ερευνούμε προσαρμοστικές ευρετικές τεχνικές για την ταξινόμηση των μεταβλητών στα ΠΙΠ. Αυτές οι τεχνικές μαθαίνουν να χρησιμοποιούν πληροφορίες από κάθε επισκεπτόμενο κόμβο του δέντρου αναζήτησης ενώ οι παραδοσιακές στατικές και δυναμικές • ευρετικες τεχνικές χρησιμοποιούν μόνο πληροφορίες σχετικά με τον αρχικό και τρέχον κόμβο. Στη συνέχεια πραγματοποιούμε μια μεγάλη εμπειρική αξιολόγηση της προτεινομένης τεχνικής και συγκρίνουμε τα αποτελέσματα που προκύπτουν με τις κυριότερες σύγχρονες στρατηγικές που υπάρχουν στη βιβλιογραφία. Όσον άφορα τη διάδοση των περιορισμών που γενικά χρησιμοποιείται ως μηχανισμός εξαγωγής συμπερασμάτων με σκοπό την απλοποίηση ενός προβλήματος έτσι ώστε να καταστεί ευκολότερη η επίλυση του ερευνούμε προσαρμοστικές στρατηγικές για την ταξινόμηση των μεταβλητών στη λίστα που δημιουργείται κατά την χρήση αλγορίθμων συνέπειας τόξου. Στη συνέχεια προτείνουμε προσαρμοστικές ευρετικές τεχνικές διακλάδωσης για τον σχηματισμό του δέντρου αναζήτησης. Η εφαρμογή αυτών των ευρετικών τεχνικών έχει ως αποτέλεσμα τη δημιουργία ενός προσαρμοστικού συστήματος διακλάδωσης. Πειράματα με τη χρήση των προτεινομένων τεχνικών επιβεβαιώνουν ότι η αναζήτηση με προσαρμοζόμενη διακλάδωση είναι αποτελεσματικότερη από την κλασσική αναζήτηση με ένα σταθερό σύστημα διακλάδωσης σε ένα ευρύ φάσμα προβλημάτων. Τέλος προτείνουμε μια νέα και γενική προσέγγιση για διακλάδωση στα ΠΙΠ όπου οι τιμές της κάθε μεταβλητής ομαδοποιούνται με βάση το σκορ υπολογίζεται από τις τεχνικές ταξινόμησης τιμών μεταβλητών σε συνεργασία με ένα αλγόριθμο ομαδοποίησης μηχανικής μάθησης. Σε γενικές γραμμές αυτή η διατριβή συμβάλλει στο σχεδιασμό και την υλοποίηση προσαρμοστικών και αυτόνομων συστημάτων επίλυσης ΠΙΠ τα οποία έχουν τη δυνατότητα να τροποποιούν επωφελώς τις αποφάσεις τους κατά τη διάρκεια επίλυσης ενός προβλήματος σε αντίθεση με τα υπάρχοντα συστήματα τα οποία λαμβάνουν αυτές τις αποφάσεις πάντα πριν την έναρξη στην αναζήτησης λύσης.