Ctrl+K

終了条件の設計

5. 終了条件の設計#

5.1. 説明#

数理最適化の文脈で定式化できた問題をシステムの一部として実運用に載せる際， 求解状態 をよく考慮して終了条件を設計する必要がある．

最適化計算が常に最適解を返すとは限らず， また最適解にしか価値がないということでもない． そして計算の失敗は直ちに実行不可能性を意味しないからである．

5.1.1. 終了条件の必要性について#

実行不可能性で計算が棄却されないならば， 計算資源が許容する限り最適解を探索するのが基本的な求解動作である． あえてプログラム言語で疑似コードを書けば，次のように while ループの挙動を想定することになる．

1while(true){
2    if(isOptimal()){
3        break;
4    }
5    search();
6}

そこでシステム構築のためには何かしらの終了条件を設計者は設定する必要がある．

注釈

ここでいう終了条件はシステムとしての終了条件であり， 何かの間違いで巨大なデータが入力として入った場合などに， システムが止まらないことを防ぐことを意図している．

これとは別に非機能要件としての終了条件がある． これらはしばしば同じ意味で扱われるが，概念としては分けた方がよいだろう．

5.1.2. 終了条件の種類と特徴#

システム設計で重要なのはユーザが設計した終了条件に適合して中断された際に， 解が実行可能解かそうでないかを判定することである． また実行可能解でない場合でもシステムの要求として緩和解を失敗と考えない場合もある．

これらの判定は Nuorium Optimizer の場合，エラーコードから判定できる． 終了条件としては求解処理時間が代表的だが，他にもいろいろとあり， エラーコードの種別と共にそれらを以下の表にまとめる．

options (C++)

デフォルト値

内容

特徴

errorCode (feas.)

errorCode (relaxed)

maxnod

-1 (無制限)

探索問題数上限

%1

17

19

maxtim

-1 (無制限)

求解処理時間上限 (単位:秒)

%1

21

22

branchObjTarget

未定義

目的関数値の閾値 (最小 (大) 化ならば閾値以下 (上))

%2

23

maxintsol

-1 (無制限)

整数解取得個数上限

%2

37

maxmem

-10 (残り 10 MiB)

消費メモリ上限 (単位:MiB)

%3

43

relgaptol

-1 (指定なし)

上下界値のギャップの相対的な閾値

%2

45

gaptol

-1 (指定なし)

上下界値のギャップの絶対的な閾値

%2

45

maxitn

%5

反復回数上限

%2 %4

0 (normal)

  • %1 : 指定した計算資源では解を得られない可能性がある．

  • %2 : 想定以上に時間がかかった場合でも，解が得られる場合はある一定水準の解となる．

  • %3 : 搭載メモリが貧弱な場合に検討する．非負値の場合は分枝限定法のメモリ利用量上限，負値の場合は残り利用可能メモリによる制限と解釈される．

  • %4 : options.method = "wcsp"; の場合には正常中断 (normal) となる．

  • %5 : 求解アルゴリズムごとにデフォルト値が異なる．内点法：150，wcsp/wls/rcpsp：-1 (無制限)

5.1.3. 例題#

C++ SIMPLE による終了条件の実装例を以下に示す．

 1options.*** = ***;
 2try{
 3    solve();
 4}
 5catch(...){
 6    printf("Internal Error!\n");
 7}
 8if(result.errorCode != 0
 9&& result.errorCode != 21
10&& result.errorCode != 23
11&& result.errorCode != 37
12&& result.errorCode != 43
13&& result.errorCode != 45){
14    printf("Failure!\n");
15}

5.2. 関連#

目次