caa a22 4500 445879246 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s10601-011-9108-5 doi (NATIONALLICENCE)springer-10.1007/s10601-011-9108-5 Hybrid search for minimal perturbation in Dynamic CSPs [Elektronische Daten] [Roie Zivan, Alon Grubshtein, Amnon Meisels] It is often the case that after a scheduling problem has been solved some small changes occur that make the solution of the original problem not valid. Solving the new problem from scratch can result in a schedule that is very different from the original schedule. In applications such as a university course timetable or flight scheduling, one would be interested in a solution that requires minimal changes for the users. The present paper considers the minimal perturbation problem. It is motivated by scenarios in which a Constraint Satisfaction Problem (CSP) is subject to changes. In particular, the case where some of the constraints are changed after a solution was obtained. The goal is to find a solution to the changed problem that is as similar as possible (e.g. includes minimal perturbations) to the previous solution. Previous studies proposed a formal model for this problem(Barták etal. 2004), a best first search algorithm(Ross et al. 2000), complexity bounds(Hebrard et al. 2005), and branch and bound based algorithms(Barták etal. 2004; Hebrard et al. 2005). The present paper proposes a new approach for solving the minimal perturbation problem. The proposed method interleaves constraint optimization and constraint satisfaction techniques. Our experimental results demonstrate the advantage of the proposed algorithm over former algorithms. Experiments were performed both on random CSPs and on random instances of the Meeting Scheduling Problem. Springer Science+Business Media, LLC, 2011 Dynamic Constraint Satisfaction Problems (CSPs) nationallicence Zivan Roie Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut Grubshtein Alon Department of Computer Science, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut Meisels Amnon Department of Computer Science, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut Constraints Springer US; http://www.springer-ny.com 16/3(2011-07-01), 228-249 1383-7133 16:3<228 2011 16 10601 https://doi.org/10.1007/s10601-011-9108-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-011-9108-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Zivan Roie Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut NATIONALLICENCE 700 1- Grubshtein Alon Department of Computer Science, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut NATIONALLICENCE 700 1- Meisels Amnon Department of Computer Science, Ben-Gurion University of the Negev, 84105, Beer-Sheva, Israel aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/3(2011-07-01), 228-249 1383-7133 16:3<228 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer