数理最適化セミナーのご案内

B.4 制約充足問題ソルバwcsp

　このアルゴリズムは離散変数，0-1整数変数を変数とした制約充足問題：

\[\begin{array}{@{}lll@{}} \mbox{変数} & x_j \in X_j, & j = 1,\cdots, n \\ \mbox{条件} & c_i^U \ge g_i(x_1,\cdots,x_j,\cdots,x_n) \ge c_i^L, & i = 1,\cdots, m \end{array}\]

をメタヒューリスティクスの解法の一つであるタブー・サーチを用いて解くものです．ここで，$X_j$は各変数の定義域に対応する有限集合です．

　本アルゴリズムは，各制約の違反量の合計を最小化する問題を解きます．近似解法であるため，制約式をすべて満たす解が存在しない場合でもできるだけ制約を満たす解を得ることができます．各制約の違反量の合計を計算する際，各制約の違反量には「重み」と呼ばれる正の定数を掛けて合算します．

　この際，重みの大きな制約式は優先的に満たされるように解の探索が行われます．

　重要度の高い制約式の重みを大きくすることで，より有用な解が期待できます．

　制約には重みを$\infty$として設定することもできます．このように設定された制約は，何よりも優先して満たすべき制約として扱われます．重みが$\infty$に設定されたものをハード制約，正の有限の値に設定されたものをソフト制約と呼びます．

　制約の他に最大化，最小化すべき目的関数$f(x_1,\cdots,x_j,\cdots,x_n)$を定義することもできますが，その際には目標値$\mu $を定めて

  • 最小化問題であれば$\mu - f(x) \ge 0$
  • 最大化問題であれば$f(x) - \mu \ge 0$

というソフト制約を定義して目的関数を扱います．つまり，目的関数自身も，あくまで満たすべき制約式のひとつとして扱われるため，目的関数に対しても重みを設定する必要があります．

　制約充足問題ソルバは，以下のいずれかの条件を満たせば停止します．

  1. すべてのハード制約およびソフト制約を満たす解が求まった（目的関数に関しては目標値を満たす解が求まった）
  2. 反復回数が指定の上限を超えた
  3. 計算時間が指定の上限を超えた
  4. ユーザが停止を命じた

　本アルゴリズムは「各制約は，それ単体でみれば容易に満たすことができる（greedy な方法でペナルティを 0 にできる）」ことを前提としています．例えば等式制約よりも不等式制約の方で記述したほうが，単体で満たしやすいため有利になる場合があります．

　本アルゴリズムは，京都大学「問題解決エンジン」グループの開発によるものです．詳細については[9], [10]をご参照ください．

B.3.2 信頼領域法を用いる方法
B.5 タブー・サーチによる資源制約スケジューリング問題解法

 

 

上に戻る