2.6 分枝限定法における出力
混合整数計画問題を解く場合は，通常，自動的に分枝限定法が起動されます．その場合[Progress]で始まるセクションでの実行経過の出力は次のようになり，求解の進行状況を確認できます．
#sol upper lower gap(%) time(s) list mem(MiB)
+inf 84121.2 +inf 2.4 1 68 cut: 44
+inf 85090.4 +inf 2.7 1 71 cut: 12
+inf 85570.3 +inf 3.0 1 74 cut: 6
#1 139000 88862.7 22.003 5.1 190 98 sol: rens
#2 135125 88862.7 20.654 5.2 190 98 sol: rens
#3 134125 89294 20.066 5.4 194 99 sol: rens
#4 134025 89294 20.030 5.5 195 99 sol: rens
#5 133850 89294 19.967 5.7 196 99 sol: rins
#6 129350 89294 18.320 5.9 197 99 sol: relax分枝限定法の進捗は，
- 新しい暫定解が得られた
- 所要メモリが50MiB以上変動した
- 15秒経過した
- （並列化機能が無効のときに）切除平面を追加した
のいずれかの条件を満たせば出力されます．
各項目の意味は次の通りです．
| 表示 | 意味 |
|---|---|
| #sol | 発見した実行可能解の個数 |
| upper | 目的関数の上界値 |
| lower | 目的関数の下界値 |
| gap(%) | 上下界の相対ギャップ（パーセンテージ） |
| time(s) | 経過時間（秒） |
| list | 探索していない分枝木の葉の数 |
| mem(MiB) | 使用メモリ（メビバイト） |
| cut | 追加した切除平面の数（並列化機能が無効であり，切除平面を追加したときに表示） |
| sol | 解を発見した手法（解を発見したときに表示） |
| #worker | 求解中のworkerの数（並列化機能が有効のときに表示） |
分枝限定法の場合は元問題とスケーリング後の問題について，非零な係数値の絶対値の範囲が出力されます．また，スケーリング値の範囲も出力されます．
Coefficient Statistics (before scaling) Coefficient range [min,max] : [1.00e-01,2.00e+01] RHS and bounds [min,max] : [1.00e+00,6.00e+01] Objective [min,max] : [1.60e+01,4.00e+01] Coefficient Statistics (after scaling) Coefficient range [min,max] : [1.75e-01,2.42e+00] RHS and bounds [min,max] : [1.00e+00,3.44e+01] Objective [min,max] : [8.60e+01,8.60e+01] Row scaling range [min,max] : [3.41e-02,3.34e+00] Column scaling range [min,max] : [3.56e-02,1.00e+00]
出力される情報は以下の5つです．
| 項目 | 意味 |
|---|---|
| Coefficient range | 係数行列において，非零要素の絶対値の範囲 |
| RHS and bounds | 制約式及び変数において，非零な上下限値の絶対値の範囲 |
| Objective | 目的関数において，非零な係数値の絶対値の範囲 |
| Row scaling range | 係数行列において，非零な行方向のスケーリング値の絶対値の範囲 |
| Column scaling range | 係数行列において，非零な列方向のスケーリング値の絶対値の範囲 |
スケーリング値は，目的関数，制約式及び変数に乗じられる定数値です．例えば列方向のスケーリング値が1.0e-08〜1.0e-6の場合は変数が「1」だけ変動すると，この変動はソルバ内部では1.0e-08〜1.0e-6という微小な変動として解釈されます．このため，内部の変数の上下限制約違反の閾値が1.0e-08であるとすると上下限制約を「1」違反する解が許容されてしまう可能性があることになります．行方向スケーリング値も同様に，制約違反の許容具合に影響します．
スケーリング値（Row scaling range / Column scaling range）が小さすぎる場合は，スケーリングオプションをoffにする，あるいは問題に与える変数の単位を見直すこと等が推奨されます．
初期解の修復機能を有効にした場合，分枝限定法の計算開始前に以下のような進捗が表示されます．
phase total_slack objective time(s) ite. mem(MiB) feas. 250.392 0 5.5 0 277 feas. 250.392 0 6.1 1 278 opt. 250.392 -6.01642e+09 24.3 2 302 feas. 2 7.59344e+08 25.2 3 301 feas. 1 7.77003e+08 25.9 4 301 feas. 1 7.77003e+08 26.5 5 293
これは初期解の修復における各反復（ite.）で，制約式の総違反量（total_slack）と目的関数（objective）がどのように遷移しているかを表示しています．行頭の feas. と opt. はその反復でどのような計算がおこなわれているかを表しています．feas. は総違反量の最小化をおこない，opt. は目的関数の最小化（あるいは最大化）をおこなっています．実行可能解が見つかるか，ある程度の反復がおこなわれると初期解の修復を終了し，分枝限定法に移行します．
上に戻る