WCSP タブーサーチ#
読み: だぶりゅーしーえすぴーたぶーさーち
英名: WCSP Tabu Search
重み付き制約充足問題 WCSP に対する解法の一つであり,茨木俊秀先生を中心とする「京都大学・問題解決エンジンプロジェクト」によって創出された. 省略して「WCSP」と呼ばれることもある.
特徴としては,タブーサーチと呼ばれるメタヒューリスティクス戦略を採用していて, タブーリスト(禁則リスト)を用いて近傍解のすべてを移動先の候補とすることを避けている. また,探索中に各制約式のペナルティの重みを内部で動的に変更することにより柔軟な探索を可能としている.
国際的コンペティションである International Nurse Rostering Competition 2010 及び International Nurse Rostering Competition 2007 において好成績を収めている.
関連
参考文献
Koji Nonobe and Toshihide Ibaraki. An Improved Tabu Search Method For The Weighted Constraint Satisfaction Problem. INFOR: Information Systems and Operational Research, 39(1):131–151, feb 2001. URL: http://www.tandfonline.com/doi/full/10.1080/03155986.2001.11732431, doi:10.1080/03155986.2001.11732431.
野々部宏司. 組合せ最適化エンジンWCSPの仕組みと実装. In 数理システムユーザーコンファレンス. 2015. URL: https://www.msi.co.jp/userconf/2015/pdf/muc15_CR6_2.pdf.