Department of Applied Mathematics & Physics, Kyoto University

Technical Report 99022 (December 27, 1999)

An Improved Tabu Search Method for the Weighted Constraint Satisfaction Problem
by Koji Nonobe and Toshihide Ibaraki

PostScript File

Various combinatorial problems arising in a wide range of applications can be formulated as constraint satisfaction problems (CSP). Aiming at developing a general problem solver, in this paper, we propose a tabu search algorithm for the weighted CSP, which is a generalization of the CSP in the sense that its constraints are weighted according to their importance. One of the features of our algorithm is to incorporate an automatic control mechanism of these weights to facilitate the search process. Using this code, we solved a number of problems including those from real applications such as generalized assignment, set covering, parallel shop scheduling, timetabling and nurse scheduling. These computational results suggest that the control mechanism of weights makes our algorithm more powerful.