TY - GEN A1 - Löffler, Sven A1 - Becker, Ilja A1 - Kroll, Franz A1 - Hofstedt, Petra T1 - A Survey of Constraint Transformation Methods T2 - 51. Jahrestagung der Gesellschaft für Informatik, INFORMATIK 2021 - Computer Science & Sustainability KW - Constraint Solving KW - Constraint Transformation KW - Optimization Y1 - 2021 UR - https://dl.gi.de/handle/20.500.12116/37760 SN - 978-3-88579-708-1 U6 - https://doi.org/10.18420/informatik2021-090 SP - 1107 EP - 1120 ER - TY - CHAP A1 - Löffler, Sven A1 - Hofstedt, Petra ED - Nicosia, Guiseppe ED - Ojha, Varun ED - Giesselbach, Sven ED - Pardalos, M. Panos ED - Umeton, Renato T1 - A constraint-based savings algorithm for the Traveling Salesman Problem T2 - Machine Learning, Optimization and Data Science : 10th International Conference, LOD 2024, Castiglione Della Pescaia, Italy, September 22-25, 2024, Revised Selected Papers N2 - There exists a plethora of NP-hard problems for which obtaining an exact solution is computationally intensive while an approximate solution can be rapidly computed. The Traveling Salesman Problem (TSP) stands out as a prominent example within this problem class, being equally significant in both research and industry sectors. Exact methods for solving the TSP are typically infeasible within acceptable timeframes beyond a certain instance size. Due to the NP-hardness of the problem, computational time requirements would quickly escalate to weeks, months, years, or even millennia. In contrast, heuristic approaches often yield sufficiently good solutions rapidly, typically within seconds or minutes. However, the drawback lies in their tendency to produce only locally optimal solutions, which may deviate significantly from a global optimum. Nevertheless, heuristic methods remain preferred in industry due to their ability to find satisfactory solutions within reasonable timeframes. It is worth noting that even marginal improvements in solutions can translate into significant cost savings in practice. Hence, there is a demand for methods capable of swiftly providing high-quality solutions while also continuously searching for further, better solutions over time. This work aims to combine two approaches: heuristic search (utilizing two simple greedy algorithms and the savings algorithm developed by Clarke and Wright) and exact search (constraint programming), to solve TSPs. Using various TSP instances, we demonstrate that our approach yields a better solution than purely local methods in at least 80% of the cases. Furthermore, within the given time limit of 5 min, the new approach identifies a solution that is more than twice as good compared to traditional COP methods. KW - Constraints KW - Optimization KW - Traveling Salesman Problem Y1 - 2025 SN - 9783031824838 U6 - https://doi.org/10.1007/978-3-031-82484-5_15 SN - 0302-9743 VL - 2 SP - 203 EP - 217 PB - Springer Nature Switzerland CY - Cham ER - TY - CHAP A1 - Assaf, George A1 - Löffler, Sven A1 - Hofstedt, Petra ED - Tack, Guido T1 - Optimized scheduling of medical appointment sequences using constraint programming T2 - Integration of constraint programming, artificial intelligence, and operations research : 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 : proceedings, Part I N2 - We propose a novel constraint-based model to efficiently tackle the medical appointment sequence scheduling problem (MASSP), inspired by a real-world problem at Charité – Universitätsmedizin Berlin. In many practical medical scenarios, scheduling a sequence of appointments, rather than a single appointment, has become increasingly essential for patients undergoing multi-stage treatments. The goal of the MASSP is to identify a set of medical resources with sufficient, consecutive, and available time slots in their calendars to create a sequence of appointments for effectively managing a treatment plan. The problem comprises various constraints, including the availability of both the intended patient and required medical resources, as well as the time and resource dependencies among the individual appointments that constitute the sequence. To address this, we formulate the problem as a constraint optimization problem () that not only captures the basic constraints of the MASSP but also optimizes resource assignment to ensure a fair workload distribution within the medical facility. The results of our experiments demonstrate that the model performs effectively under diverse conditions, which confirms the utility and robustness of the proposed model in optimizing resource allocation and ensuring equitable workload distribution. KW - Constraint Programming KW - Optimization KW - Medical Appointment Scheduling Y1 - 2025 SN - 978-3-031-95973-8 U6 - https://doi.org/10.1007/978-3-031-95973-8_1 SN - 0302-9743 SP - 1 EP - 16 PB - Springer Nature Switzerland CY - Cham ER - TY - GEN A1 - Assaf, George A1 - Löffler, Sven A1 - Hofstedt, Petra ED - Rocha, Ana Paula ED - Steels, Luc ED - van den Herik, H. Jaap T1 - Constraint-based optimization for scheduling medical appointments T2 - Proceedings of the 17th International Conference on Agents and Artificial Intelligence : volume 3: ICAART, 94-103, 2025 , Porto, Portugal N2 - In this paper, we introduce a novel approach for solving as well as optimizing the medical appointment scheduling problem (MASP) using constraint programming. The MASP is a complex and critical task in health care management, directly impacting both patient care and operational efficiency. We formalize the MASP as a set of constraints that encode diverse requirements for scheduling medical appointments, including intuitive requirements such as the availability of both patients and medical resources, including physicians, nurses and medical equipment. Furthermore, our model accounts for patient preferences, such as favoring specific dates and/or particular resources whenever feasible. The proposed method incorporates optimization techniques that enhance the scheduling process by considering appointment urgency and balancing workload distribution among the assigned resources, thereby improving the allocation of medical resources. As an outcome, our constraint model demonstrates high ef ficiency by scheduling medical appointments in just milliseconds. KW - Constraint Programming KW - Optimization KW - Medical Appointment Scheduling Y1 - 2025 SN - 978-989-758-737-5 U6 - https://doi.org/10.5220/0013091300003890 SP - 94 EP - 103 PB - SciTePress - Science and Technology Publications CY - Setúbal, Portugal ER -