トップ > 数理計画用語集 > WCSP

数理計画用語集

WCSP

読み:だぶりゅーしーえすぴー

重み付き制約充足問題のことであり,英語表記の頭文字をとり WCSP と呼んでいる.これは,重要な制約条件をなるべく満足するためには値をどのように割り当てるとよいかを決定する問題である.

CSP制約充足問題)との大きな違いは,制約条件の重要度を表現できるか否かである.CSP では解は全ての制約を必ず満たす必要がある.一方,WCSP では制約条件の重要度を重みとして設定できる.このため,制約の充足具合に関するモデル作成者の意向が反映された解を求めることが可能になる.この特徴を生かし,WCSP は個人の希望をなるべく満たすように必要な人員を割り当てるという問題などに応用されている.

Numerical Optimizer にはメタヒューリスティクス解法の一つであるタブーサーチを用いこの問題を解くアルゴリズムが搭載されており,こちらも WCSP と呼ぶ.なお,このアルゴリズムは茨木俊秀先生を中心とする「京都大学・問題解決エンジンプロジェクト」により生み出されたものである.