Βελτίωση απόδοσης επιλυτών σε προβλήματα χρονοπρογραμματισμού μέσω μοντελοποίησης εξάλειψης συμμετριών

Abstract

Symmetry is a pervasive and often problematic feature in combinatorial optimization problems, particularly in scheduling and timetabling. While symmetry is traditionally associated with elegance and balance in mathematics and the sciences, in optimization it frequently leads to redundant search spaces, inefficiencies, and computational bottlenecks. This thesis investigates the role of symmetry in a variety of combinatorial optimization contexts, with a focus on its identification, elimination, and exploitation to improve solution quality and computational performance. The work begins with a theoretical foundation, exploring symmetry in linear, mixed-integer, constraint, and quadratic programming, as well as in metaheuristics, QUBO, and SAT formulations. It then presents five detailed case studies: the Uncapacitated Examination Timetabling Problem (UETP), Post Enrollment Course Timetabling (PE-CTT), Thesis Defense Timetabling Problem (TDTP), Sports Scheduling, and One-Machine Scheduling with Time-Dependent Capacity. Each case study demonstrates how symmetry manifests in real-world datasets and how its careful handling can lead to significant improvements in solution quality and solver efficiency. The thesis introduces novel symmetry-breaking constraints, reformulations, and hybrid methodologies, including exact and heuristic approaches. Notably, it proposes a QUBO-based model for UETP suitable for quantum annealers, a hybrid framework for PE-CTT, and a symmetry-aware CP model for TDTP that achieves near-optimal results. In the sports scheduling domain, the work contributes to the ITC2021 competition with a constraint programming-based solver. Finally, a hybrid exact-local search method is developed for the one-machine scheduling problem, outperforming state-of-the-art memetic algorithms. The findings underscore the critical importance of symmetry handling in combinatorial optimization and provide a comprehensive toolkit for researchers and practitioners seeking to enhance solver performance across diverse problem domains.

Η συμμετρία αποτελεί ένα διαδεδομένο και συχνά προβληματικό χαρακτηριστικό στα προβλήματα συνδυαστικής βελτιστοποίησης, ιδιαίτερα στον προγραμματισμό και την κατάρτιση χρονοδιαγραμμάτων. Αν και η συμμετρία συνδέεται παραδοσιακά με την κομψότητα και την ισορροπία στα μαθηματικά και τις επιστήμες, στη βελτιστοποίηση οδηγεί συχνά σε πλεονάζοντες χώρους αναζήτησης, αναποτελεσματικότητα και υπολογιστικά εμπόδια. Η παρούσα διατριβή διερευνά τον ρόλο της συμμετρίας σε διάφορα πλαίσια συνδυαστικής βελτιστοποίησης, με έμφαση στην αναγνώριση, την εξάλειψη και την αξιοποίησή της για τη βελτίωση της ποιότητας των λύσεων και της υπολογιστικής απόδοσης. Η εργασία ξεκινά με μια θεωρητική θεμελίωση, εξετάζοντας τη συμμετρία στον γραμμικό, μικτό ακέραιο, προγραμματισμό ύπο περιορισμούς και τετραγωνικό προγραμματισμό, καθώς και σε μεταευρετικούς αλγορίθμους, QUBO και SAT διατυπώσεις. Στη συνέχεια παρουσιάζονται πέντε λεπτομερείς μελέτες περίπτωσης: το πρόβλημα κατάρτισης εξεταστικού προγράμματος χωρίς χωρητικότητα, το πρόβλημα κατάρτισης προγράμματος μαθημάτων μετά την εγγραφή , το πρόβλημα κατάρτισης προγράμματος υποστηρίξεων διπλωματικών εργασιών, ο προγραμματισμός αθλητικών διοργανώσεων και ο προγραμματισμός μηχανής με χρονικά εξαρτώμενη χωρητικότητα. Κάθε μελέτη περίπτωσης δείχνει πώς εκδηλώνεται η συμμετρία σε πραγματικά δεδομένα και πώς η προσεκτική διαχείρισή της μπορεί να οδηγήσει σε σημαντικές βελτιώσεις στην ποιότητα των λύσεων και την αποδοτικότητα των επιλυτών. Η διατριβή εισάγει νέους περιορισμούς διάσπασης συμμετρίας, αναδιατυπώσεις και υβριδικές μεθοδολογίες, συμπεριλαμβανομένων ακριβών και ευρετικών προσεγγίσεων. Ιδιαίτερα, προτείνεται ένα μοντέλο βασισμένο σε QUBO για το UETP κατάλληλο για κβαντικούς υπολογιστές, ένα υβριδικό πλαίσιο για το PE-CTT και ένα μοντέλο CP με επίγνωση συμμετρίας για το TDTP που επιτυγχάνει σχεδόν βέλτιστα αποτελέσματα. Στον τομέα του αθλητικού προγραμματισμού, η εργασία συμβάλλει στον διαγωνισμό ITC2021 με έναν επιλυτή βασισμένο στον προγραμματισμό περιορισμών. Τέλος, αναπτύσσεται μια υβριδική μέθοδος ακριβούς-τοπικής αναζήτησης για το πρόβλημα προγραμματισμού μηχανής, η οποία ξεπερνά τους πιο σύγχρονους μιμητικούς αλγορίθμους.Τα ευρήματα υπογραμμίζουν τη ζωτική σημασία της διαχείρισης της συμμετρίας στη συνδυαστική βελτιστοποίηση και παρέχουν ένα ολοκληρωμένο εργαλείο για ερευνητές και επαγγελματίες που επιδιώκουν να ενισχύσουν την απόδοση των επιλυτών σε ποικίλους τομείς προβλημάτων.