TY - CHAP A1 - Hofstedt, Petra ED - Görz, Günther ED - Schneeberger, Josef ED - Schmid, U. T1 - Constraints T2 - Handbuch der Künstlichen Intelligenz Y1 - 2013 SN - 978-3-486-71307-7 SN - 978-3-486-71979-6 SP - 205 EP - 234 PB - Oldenburg Verlag CY - München ET - 5. korrigierte Auflage ER - TY - CHAP A1 - Hinze, Thomas A1 - Behre, Jörn A1 - Bodenstein, Christian A1 - Escuela, Gabi A1 - Grünert, Gerd A1 - Hofstedt, Petra A1 - Sauer, Peter A1 - Hayat, Sikander A1 - Dittrich, Peter ED - Paun, G. T1 - Membrane Systems and Tools Combining Dynamical Structures with Reaction Kinetics for Applications in Chronobiology T2 - Applications of Membrane Computing in Biology, Springer Series Emergence, Complexity, and Computation, 2013 Y1 - 2013 PB - Springer-Verlag CY - Berlin ER - TY - CHAP A1 - Hofstedt, Petra A1 - John, Ulrich A1 - Wolf, Armin ED - Eibl, Maximilian ED - Gaedke, Martin T1 - MOC 2017 – 9. Workshop zur Deklarativen Modellierung und effizienten Optimierung komplexer Probleme T2 - 47. Jahrestagung der Gesellschaft für Informatik, Informatik 2017 KW - Deklarative Programmierung Y1 - 2017 UR - https://dl.gi.de/handle/20.500.12116/4076 SN - 978-3-88579-669-5 U6 - https://doi.org/10.18420/in2017_56 SN - 1617-5468 PB - GI CY - Bonn ER - TY - CHAP A1 - Hofstedt, Petra A1 - Hower, Walter A1 - John, Ulrich A1 - Wolf, Armin ED - Draude, Claude ED - Lange, Martin ED - Sick, Bernhard T1 - MOC 2019 - 11. Workshop zur transparenten Modellierung und Optimierung komplexer Probleme T2 - INFORMATIK 2019 - 50 Jahre Gesellschaft für Informatik - Informatik für Gesellschaft Y1 - 2019 UR - https://dl.gi.de/handle/20.500.12116/25099 SN - 978-3-88579-689-3 U6 - https://doi.org/10.18420/inf2019_ws40 PB - GI CY - Bonn ER - TY - CHAP A1 - Hofstedt, Petra A1 - Löffler, Sven ED - Görz, Günther ED - Schmid, Ute ED - Braun, Tanya T1 - Constraints T2 - Handbuch der künstlichen Intelligenz KW - Constraints Y1 - 2021 UR - https://www.degruyter.com/view/title/558044 SN - 978-3-11-065984-9 SN - 978-3-11-065994-8 SN - 978-3-11-065995-5 U6 - https://doi.org/10.1515/9783110659948-016 SP - 713 EP - 754 PB - De Gruyter CY - Berlin, Boston ET - 6. Auflage 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 - Löffler, Sven A1 - Hofstedt, Petra ED - Rocha, Ana Paula ED - Steels, Luc ED - van den Herik, H. Jaap T1 - Greedy and local search-based constraint optimization of the travelling salesman problem T2 - Agents and Artificial Intelligence : 16th International Conference, ICAART 2024 Rome, Italy, February 24–26, 2024 : revised selected papers, Part II N2 - Constraint optimization problems offer a way to obtain a global solution for a given problem. However, the promise of finding a global solution often comes at the cost of significant time and computational resources. Greedy search, local search, and cluster identification methods represent alternative approaches, which can quickly lead to local optima. In our previous work presented at the 16th International Conference on Agents and Artificial Intelligence (ICAART) 2024 [19], we introduced new methods to combine constraint programming with greedy search and clustering methods in the context of the traveling salesman problem. In this paper, we explore the advantages of incorporating greedy search and local search, which can be seen as a clustering technique in this case, into constraint optimization methods without forsaking the pursuit of a global solution. The global search process is initially designed to behave similarly to a greedy search or local search. Compared to [19], we now considered more diverse greedy and iterated local search techniques as a new clustering method. Our approach aims to achieve two key objectives: first, to accelerate the process of finding of an initial solution, and second, to ensure that this solution possesses a high level of optimality. Our approach is an enhancement of the general branch-and-bound method in constraint programming. Finally, we validate our results using the traveling salesman problem as a case study. KW - Constraint Optimization KW - Informed and local search KW - Travelling Salesman Problem KW - TSP Y1 - 2025 SN - 9783031873294 U6 - https://doi.org/10.1007/978-3-031-87330-0_11 SN - 0302-9743 SP - 212 EP - 233 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 - CHAP A1 - Löffler, Sven A1 - Hofstedt, Petra ED - Gini, Giuseppina ED - Nijmeijer, Henk ED - Filev, Dimitar T1 - Enhanced optimal beacon placement for indoor positioning : refining the search process T2 - Informatics in control, automation and robotics : 20th International Conference, ICINCO 2023, Rome, Italy, November 13–15, 2023 : revised selected papers N2 - Indoor localization plays a key role across diverse environments such as hospitals, retirement homes, and emergency response scenarios. Ensuring the efficient and precise tracking of mobile individuals indoors heavily relies on the strategic deployment of sensors. Manual placement of beacons (sensors) for indoor positioning within a building poses significant challenges and time constraints. Consequently, numerous researchers have explored this problem domain, employing diverse algorithms and addressing various practical scenarios. In our previous works at the ACS/IEEE International Conference on Computer Systems and Applications (AICCSA 2022) [20] and the 20th International Conference on Informatics in Control, Automation and Robotics (ICINCO 2023) [19], we introduced two novel approaches that leverage constraint programming with exclusively Boolean variables respectively only set variables and Boolean variables to efficiently place Bluetooth Low Energy (BLE) beacons in indoor scenarios. We evaluated the quality of our results by comparing them against manually optimized beacon placement and assessing their performance in four real-world school buildings. This paper extends the findings of [19, 20] by new approaches on the search in the constraint solving process using greedy search and local search techniques. KW - Constraint Programming KW - Search Methods KW - Beacon Placement Y1 - 2025 SN - 978-3-031-94989-0 U6 - https://doi.org/10.1007/978-3-031-94989-0_5 SN - 1876-1100 SP - 97 EP - 124 PB - Springer Nature Switzerland CY - Cham ER - TY - CHAP A1 - Löffler, Sven A1 - Abbenhaus, Viktoria A1 - Assaf, George A1 - Hofstedt, Petra ED - Braun, Tanya ED - Paaßen, Benjamin ED - Stolzenburg, Frieder T1 - A hybrid constraint-based, greedy, and local search approach for the transshipment problem T2 - KI 2025 : advances in artificial intelligence : 48th German Conference on AI, Potsdam, Germany, September 16–19, 2025 : proceedings N2 - The efficient resolution of logistics problems, particularly those aimed at minimizing costs and reducing environmental impact, represents a critical challenge in our globalized world. A prominent example of such problems is the Transshipment Problem, which seeks to determine the most cost-effective paths from sources (e.g., producers) through transshipment points to sinks (e.g., customers). Approaches to addressing this problem range from greedy algorithms, which may rapidly yield locally optimal solutions, to constraint-based methods that, given sufficient resources and computation time, can identify globally optimal solutions. In this study, we propose a hybrid approach that integrates greedy strategies into the solution process of constraint modeling for the Transshipment Problem. This integration aims to expedite the discovery of high-quality initial solutions while preserving the global optimization capabilities inherent in constraint-based search methods. To validate the effectiveness of this new hybrid approach, we conducted an extensive series of experiments, which demonstrate its significant advantages in solving the Transshipment Problem compared to both a conventional constraint model and pure greedy methods. KW - Constraint Programming KW - Search methods KW - Transshipment problem Y1 - 2025 SN - 978-3-032-02813-6 U6 - https://doi.org/10.1007/978-3-032-02813-6_7 SN - 0302-9743 SP - 91 EP - 103 PB - Springer Nature Switzerland CY - Cham ER -