6.1 wcspを用いる場合の注意点
アルゴリズムとして制約充足問題ソルバwcspを用いる際には,wcspは近似解法であり必ずしも厳密解が求まるわけではない点に注意してください.
また,他のアルゴリズムと異なり幾つかの制限があります.1つは実数変数Variable
を用いることができないこと.もう1つは制約式や目的関数において小数点以下が切り捨てられることです.以下で詳しく説明します.
wcspは変数として0-1整数変数(type = binary
としたIntegerVariable
)と離散変数(DiscreteVariable
)を用いて定式化します.連続変数や,0-1整数変数でない整数変数は用いることが出来ません.以下,wcspで用いることができる構成要素を説明します.
構成要素名 | C++SIMPLE内の名称 | 機能 |
---|---|---|
目的関数 | Objective |
目的関数を表す |
制約式 | Constraint |
制約式を表す |
定数 | Parameter |
定数を表す |
整数変数 | IntegerVariable |
整数変数を表す |
範囲演算関数 | sum |
|
式 | Expression |
頻出する数式に対して,簡単な別の表現を与える |
添字 | Element |
添字を表す |
集合 | Set |
添字の動く範囲を表す |
順序集合 | OrderedSet |
要素間に順序を持つ集合を表す |
数列集合 | Sequence |
等差数列からなる集合を表す |
条件式 | 制約式や代入文を制限する | |
数学関数 | exp , sin , cos , log ...
|
数学関数を表す |
離散変数 | DiscreteVariable |
離散変数を表す |
重複不能関数 | alldiff |
重複不能を表す |
選択関数 | selection |
限定選択を表す |
ハード制約関数 | hardConstraint |
ハード制約を表す |
セミハード制約関数 | semiHardConstraint |
セミハード制約を表す |
ソフト制約関数 | softConstraint |
ソフト制約を表す |
冒頭で述べた小数点以下が切り捨てられる点について説明します.wcspは制約式や目的関数をペナルティとして認識し,ペナルティが小さくなる答えを探すアルゴリズムです.Nuorium Optimizerの内部でこのペナルティを評価する際に小数点以下を切り捨て,整数として評価を行います.
例えば,という制約式があったとします.このとき,
における制約式の違反量は
に対して小数点以下の切り捨てが適用され, 1となります.
このように,「評価した後に切り捨てが適用される」というのが特徴です.定式化の段階で小数点以下も考慮する必要がある目的関数や制約式に関しては,該当する式(制約式ならば両辺)に大きな値(1000ならば小数第三桁まで有効になる)をかけておく必要があります注1.
注1)ただし値が極端に大きくならないよう注意してください.
上に戻る