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

5.7.21 分枝限定法における初期解修復

オプション名

モデリング言語/nuopt.prm オプション名 型
PySIMPLE Problem.options.branchRepairSolution シンボル
C++SIMPLE options.branchRepairSolution 文字列値
RSIMPLE なし -
nuopt.prm branch:repairSolution 文字列値

設定値

型 文字列値 シンボル
デフォルト値 off Branch.RepairSolution.OFF
値範囲 {off, on, aggressive} {Branch.RepairSolution.OFF,
Branch.RepairSolution.ON,
Branch.RepairSolution.AGGRESSIVE}


文字列値 シンボル 意味
off Branch.RepairSolution.OFF 初期解修復機能をオフにする
on Branch.RepairSolution.ON 初期解修復機能をオンにする
aggressive Branch.RepairSolution.AGGRESSIVE 初期解修復機能をオンにして積極的な探索を行う

詳細
  • 本オプションは初期解修復機能を制御します．
  • 初期解修復機能とは，与えた初期解から，制約違反量及び目的関数値を最適化して良質な実行可能解を得る機能です．例えば，制約条件を満たさない実行不可能な解が与えられたときも，これを修復して実行可能解を得ることができます．
  • 初期解修復機能は分枝限定法の前段階（前処理を行う前）で実行されます．本機能が停止した段階で実行可能解が得られた場合，解を初期解として分枝限定法が実行されます．
  • 初期解修復機能では解を修復するためには 2 段階の求解を繰り返します（[21]）．
    • 1 段階目では，実行不可能性（制約条件の違反量）を最小化します．これは元の数理最適化問題と同等に難しいため，一部の整数変数を固定することで問題規模を縮小して求解します．
    • 2 段階目では，実行不可能性に上限を与え，その範囲内で元の目的関数を最適化します．ここでも一部整数変数を固定して問題規模を縮小します．
    • 2 段階の求解を繰り返すことで実行不可能性を最小化することにより実行可能解を得ます．
  • 初期解修復機能で用いる初期解について，連続変数には初期値を与える必要はありません．整数変数には上下限制約を満たす初期値を設定します．
  • 「分枝限定法におけるスレッド数上限」を 2 以上に設定した場合は本機能も並列実行されます．その場合，より少ない反復で解が修復されます．スレッド数を増やすと初期解修復機能によって実行可能解が得られる可能性も高まります．
  • 初期解修復機能は以下の停止条件を満たすと停止します．
    1. 2 つ以上の実行可能解を発見した
    2. 制約違反量または目的関数値が小さくなる解を 3 回連続して発見できなかった
    3. 反復回数が，設定された「分枝限定法における初期解修復の回数」を超過（設定されていない場合はデフォルト値を超過）
    4. 設定された「計算時間上限」を超過
    5. 設定された「分枝限定法におけるメモリ上限」を超過
  • 本オプション値を aggressive/Branch.RepairSolution.AGGRESSIVE に設定した場合，停止条件 1. と 2. を無視します．
関連
  • 5.7.19 分枝限定法におけるスレッド数上限
  • 5.2.3 計算時間上限
  • 5.7.15 分枝限定法におけるメモリ上限
  • 5.7.22 分枝限定法における初期解修復の回数上限
5.7.20 分枝限定法における並列化手法
5.7.22 分枝限定法における初期解修復の回数上限

 

 

上に戻る