Back to search

University of Ioannina

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

Abstract

dc:description

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.

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 × 8

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/59597

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Dimitsas, Angelos; Δήμητσας, Άγγελος. Βελτίωση απόδοσης επιλυτών σε προβλήματα χρονοπρογραμματισμού μέσω μοντελοποίησης εξάλειψης συμμετριών. University of Ioannina, 2025. http://hdl.handle.net/10442/hedi/59597