5.7.16 分枝限定法における上下界値ギャップ閾値（相対値）

オプション名

モデリング言語/nuopt.prm	オプション名
PySIMPLE	Problem.options.branchRelativeGapTolerance
C++SIMPLE	options.relgaptol
RSIMPLE	なし
nuopt.prm	branch:relgaptol

設定値

値	意味
$< 0$	ギャップ閾値を設定しない
$>= 0$	上下界のギャップ値の相対値が指定値を下回ったら停止する

詳細

分枝限定法は実行中の上界と下界がもとまります．例えば，最小化問題の場合は実行可能解の目的関数値が上界となります．上下界ギャップ値とは，この上界と下界の差を表します．
上下界ギャップ値の相対値が指定した値を下回る場合に解の探索を停止します．停止した際は，以下のエラーが出力されます．
```
(NUOPT 45) Gap in branch-and-bound method reaches below the limit.
```
上下界値のギャップは実行可能解が求まったときにのみ意味を持ちます．したがってこのエラーで停止した場合には必ず実行可能解の出力がされます．
ギャップ閾値の設定方法として，絶対値で指定する方法と相対値で指定する方法の二つがあります．本オプションは相対値で指定します．
ギャップの相対値は，上界値を $Z_p$ ，下界値を $Z_d$ とした時，以下で定義されます．
$relgap := \begin{cases} 0, & Z_p = Z_d = 0 \\ \frac{| Z_p - Z_d | }{\max{(| Z_p |, | Z_d |)}}, & Z_p \cdot Z_d \ge 0 \\ 1, & Z_p \cdot Z_d < 0 \end{cases}$

Nuorium Optimizer マニュアル V27