Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems

Abstract

Constraint Programming (CP) is a successful technology for solving a wide range of problemsin business and industry which require the satisfaction of a set of complex constraints.Examples include product configuration, resource allocation, transportation, andscheduling. As the simultaneous satisfaction of different constraints is intractable in general,problems can become very difficult to solve as their size increases. CP has thusdeveloped various techniques to tackle this inherent problem. Enforcing a local consistencyproperty is one of the most important such techniques.Bounds Consistency (BC) and Generalised Arc Consistency (GAC) are the two mostwidely studied and used local consistencies in CP solvers. While there exist strongerlocal consistency (SLC) properties, their usage is limited due to their prohibitive cost.Examples are max Restricted Path Consistency (maxRPC) and max Restricted PairWiseConsistency (maxRPWC).In our research, we propose efficient filtering algorithms for enforcing SLCs. In particular,we propose new algorithms for maxRPC and maxRPWC that advance the existingalgorithms (theoretically and practically). We also propose algorithms that achieve weakerconsistencies with a lower cost. In addition, we have extended the recent algorithms fromthe family of Simple Tabular Reduction (STR) to achieve a higher-order local consistencyproperty. Experiments demonstrate that these algorithms can significantly outperformvarious state-ot the-art (G)AC algorithms, even by orders of magnitude, and thus can becomevery useful additions to the propagation techniques that CP solvers currently apply.Additionally, we have introduced and defined a new strong Bounds Consistency, calledPWBC, as well as a polynomial filtering algorithm based on this consistency for the importantclass of linear inequalities. Theoretical and experimental results demonstrate thepotential of SLCs that reason on bounds.Finally, since SLCs may still be too expensive to maintain during search in manyproblems, we have suggested ways to interleave them with weaker propagation methodssuch as GAC. We have proposed fully automated heuristics that can dynamically selectthe most appropriate filtering algorithm. All algorithms are incorporated in an adaptivefiltering scheme to further tackle the inherent difficulty of constraint satisfaction, resultingin a more robust constraint solver. Overall, this research proposes filtering algorithms andadaptive techniques that exploit the filtering power offered by SLCs in an efficient way, inorder to increase the efficacy of CP solvers.

Ο Προγραμματισμός με Περιορισμούς (Constraint Programming - CP) είναι μια επιτυχημένητεχνολογία για την επίλυση πολλών προβλημάτων από το χώρο των επιχειρήσεων και τηςβιομηχανίας, που απαιτούν την ικανοποίηση μιας σειράς πολύπλοκων περιορισμών.Παραδείγματα τέτοιων προβλημάτων είναι η διαμόρφωση προϊόντος, η κατανομή πόρων, ταπροβλήματα μεταφοράς και χρονοπρογραμματισμού. Επειδή η ταυτόχρονη ικανοποίηση τωνδιαφόρων περιορισμών είναι γενικά δυσεπίλυτη, τα προβλήματα μπορεί να γίνουν ακόμηδυσκολότερα καθώς αυξάνει το μέγεθός τους. Ο Προγραμματισμός με Περιορισμούς έχειαναπτύξει διάφορες τεχνικές για να αντιμετωπίσει αυτό το εγγενές πρόβλημα. Μια από τις πιοσημαντικές τέτοιες τεχνικές είναι η εφαρμογή τοπικής συνέπειας.Οι τοπικές συνέπειες που έχουν ευρέως μελετηθεί και χρησιμοποιηθεί από συστήματαεπίλυσης είναι η συνέπεια ορίων (Bounds Consistency - BC) και η συνέπεια τόξου (ArcConsistency - AC). Παρότι έχουν προταθεί και ισχυρότερες τοπικές συνέπειες, η χρήση τους είναιπεριορισμένη λόγω του απαγορευτικού κόστους τους. Παραδείγματα αποτελούν οι συνέπειες maxRestricted Path Consistency (maxRPC) και max Restricted PairWise Consistency (maxRPWC).Στην παρούσα έρευνα προτείνουμε αποδοτικούς αλγόριθμους ελέγχου συνέπειας για τηνεπιβολή ισχυρών τοπικών συνεπειών. Συγκεκριμένα, προτείνουμε νέους αλγόριθμους για τιςσυνέπειες maxRPC και maxRPWC που βελτιώνουν (θεωρητικά και πρακτικά) τουςπροηγούμενους. Επίσης, προτείνουμε αλγόριθμους που εφαρμόζουν ασθενέστερες συνέπειες μεχαμηλότερο κόστος, έχουμε επεκτείνει τους πρόσφατους από την οικογένεια των STR (SimpleTabular Reduction) αλγορίθμων για την επίτευξη υψηλότερης τάξης (higher-order) τοπικήςσυνέπειας. Πειράματα δείχνουν ότι αυτοί οι αλγόριθμοι μπορούν να ξεπεράσουν state-ot-the-artAC αλγόριθμους με σημαντικές διαφορές, ακόμη και κατά τάξεις μεγέθους, και συνεπώς, μπορούννα αποτελέσουν χρήσιμες προσθήκες στις τεχνικές διάδοσης περιορισμών για τους σύγχρονουςCP επιλυτές. Επιπρόσθετα, εισάγουμε και ορίζουμε μια νέα ισχυρή συνέπεια ορίων, πουονομάζεται PWBC, καθώς και έναν πολυωνυμικό αλγόριθμο ελέγχου συνέπειας που βασίζεται σεαυτήν για την σημαντική κατηγορία των γραμμικών ανισοτήτων. Τα θεωρητικά και πειραματικάαποτελέσματα αναδεικνύουν τις δυνατότητες των ισχυρών συνεπειών που επιβάλλονται στα όρια.Τέλος, δεδομένου ότι οι ισχυρές συνέπειες μπορεί να εξακολουθούν να είναι ακριβές στηνεφαρμογή τους κατά την αναζήτηση σε πολλά προβλήματα, προτείνουμε τρόπους ώστε ναπαρεμβάλλονται μαζί με ασθενέστερες συνέπειες, όπως η συνέπεια τόξου. Προτείνουμε πλήρωςαυτοματοποιημένες ευρετικές μεθόδους, που μπορούν να επιλέξουν δυναμικά τον καταλληλότεροαλγόριθμο φιλτραρίσματος. Οι προτεινόμενοι αλγόριθμοι ενσωματώνονται σε ένα προσαρμοστικόσύστημα διάδοσης περιορισμών για να αντιμετωπίσει περαιτέρω την εγγενή δυσκολίαικανοποίησης περιορισμών, με αποτέλεσμα έναν ισχυρότερο επιλυτή. Συνολικά, η έρευναπροτείνει αλγόριθμους φιλτραρίσματος και προσαρμοστικές τεχνικές που εκμεταλλεύονται τομεγάλο φιλτράρισμα των ισχυρών συνεπειών με αποτελεσματικό τρόπο, προκειμένου να αυξηθείη αποτελεσματικότητα των CP επιλυτών.