Search Space Sampling by Simulated Annealing for Identifying Robust Solutions in Course Timetabling

摘要

For many combinatorial optimization problems, it is important to identify solutions that can be repaired without degrading solution quality in case changes in the data associated with the constraints make the initial solution infeasible, while ensuring that the new solution is not too different from the initial one. We propose a novel approach for finding such robust solutions based on a sample of solutions picked from the search space traversed by a simulated annealing algorithm. The sampled solutions are used to form a network of solutions. To explore the practical performance of this approach, we solve the widely studied curriculum-based course timetabling problem of the International Timetabling Competition 2007. With these benchmark instances, and sets of randomly generated disruption scenarios, we analyze the performance of some network-based estimators and show that the diversity of its neighbors is a significant indicator of a solution’s robustness.