University of Ioannina
Βελτίωση απόδοσης επιλυτών σε προβλήματα χρονοπρογραμματισμού μέσω μοντελοποίησης εξάλειψης συμμετριών
Abstract
dc:descriptionSymmetry 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.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Dimitsas, Angelos
- Δήμητσας, Άγγελος
Subjects
dc:subject × 8Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/59597