In many scheduling and resource assignment problems, it is necessary to find a solution which is as similar as possible to a given, initial assignment. We propose a new algorithm for this minimal perturbation problem which searches a space of variable commitments and uses a lower bound function based on the minimal vertex covering of a constraint violation graph. An empirical evaluation on random CSPs show that our algorithm significantly outperforms previous algorithms, including the recent two-phased, hybrid algorithm proposed by Zivan, Grubshtein, and Meisels.
展开▼
