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
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.