Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems
Authors: Παπαρρίζου Αναστασία 
Published: August 2021

Ο Προγραμματισμός με Περιορισμούς (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 επιλυτών.