3.4. 制約充足問題ソルバ wcsp/wls#

制約充足問題とは制約条件を満たす解を見つける組合せ最適化問題です． PySIMPLE では制約充足問題に対するメタヒューリスティクスアルゴリズムとして， wcsp(weighted constraint satisfaction problem)，wls(weighting local search)を用いることができます．制約充足問題ソルバを用いる場合は他のアルゴリズムと異なり近似解法であり，厳密解である保証がありません．

wcsp と wls の違いは以下のとおりです．

	wcsp	wls
探索方法	タブー探索	局所探索
近傍操作	一度に最大 2 つの変数の値を変更	一度に最大 4 つの変数の値を変更
探索傾向	実行可能解の早期発見を目的とした探索	目的関数・ソフト制約を重視した上で実行可能解を探索
連続変数	非対応	対応 [1]
添字グループ	非対応	割当を表す変数への指定により探索範囲を拡大 [2]
目的関数	目標値を用いたソフト制約化	目的関数のまま扱う
Selection 制約	充足を保ちながら探索	制約式へ変換，探索戦略を修正
セミハード制約	対応	非対応（ハード制約へ変換）
制約違反量	整数値へ変換（小数点以下切捨て） [3]	実数値のまま扱う
C++SIMPLE	対応	非対応
得意な問題例	選択・割当を表す変数が多い問題．特に，Selection を多く含むモデル．	選択・割当を表す変数が多い問題．特に，係数が 0-1 の制約式が多い問題（集合被覆制約など）．また，充足の難しい制約式をもつ問題（集合分割制約・等号ナップサック制約など）．

[3]

wcsp/wls は制約式や目的関数をペナルティとして認識し，ペナルティが小さくなる答えを探すアルゴリズムです． Nuorium Optimizer の内部でこのペナルティを評価する際に小数点以下を切り捨て，整数として評価を行います．よって，「0 >= 1」のような制約式は制約違反（ペナルティ1）となりますが，「0 >= 0.99」というような制約式は制約を満たしている（ペナルティ0）となります．定式化の段階で小数点以下も考慮する必要がある目的関数や制約式に関しては，該当する式（制約式ならば両辺）に大きな値（1000ならば小数第三桁まで有効になる）をかけておく必要があります．ただし値が極端に大きくならないよう注意してください．

制約充足問題ソルバではハード制約，セミハード制約，ソフト制約といった制約式種の活用が有効です．詳細は制約式種をご覧ください．