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

2.4 単体法（hsimplex）における出力

　本節では，単体法（hsimplex）実行時に標準出力に表示されるログについて説明します．

　ログは大きく次のフェーズに分けて出力されます．

  1. LP folding
  2. Presolve
  3. Progress（単体法の反復ログ）
  4. Postsolve
  5. LP unfolding

　以下では，それぞれのフェーズにおける出力内容について説明します．

　

　1. [LP-Folding]

　LP folding は，問題に内在する対称性を検出し，問題を縮小（折り畳み）する処理です．

[LP-Folding]
  before : 14646 rows, 23968 columns, 133184 nonzeros
  after  : 6190 rows, 6505 columns, 37043 nonzeros
Compression Ratio
  rows     : 1.000 -> 0.423
  columns  : 1.000 -> 0.271
  nonzeros : 1.000 -> 0.278
sufficient reduction detected, applying LP folding

　各項目の意味は次の通りです．

項目 意味
before Folding 前の行数・列数・非ゼロ要素数
after Folding 後の行数・列数・非ゼロ要素数
Compression Ratio 問題サイズの縮小率を 1.0（元の大きさ）に対する比として表示

　

　LP folding を適用するかどうかは，縮小率などを考慮してソルバー内部で自動的に判断されます．十分な縮小が得られた場合には，LP folding を適用し，次のメッセージが表示されます．

sufficient reduction detected, applying LP folding

　一方，十分な縮小が得られない場合には，次のメッセージが表示されます．

reduction not sufficient, skipping LP folding

　

　2. [Presolve]

　Presolve は，固定変数の代入，冗長制約の削除，変数上下限のタイト化などにより問題を縮小する前処理です．

[Presolve]
  before : 6190 rows, 6505 columns, 37043 nonzeros
  after  : 4016 rows, 4624 columns, 26014 nonzeros
Compression Ratio
  rows     : 1.000 -> 0.649
  columns  : 1.000 -> 0.711
  nonzeros : 1.000 -> 0.702

　各項目の意味は次の通りです．

項目 意味
before Presolve 前の行数・列数・非ゼロ要素数
after Presolve 後の行数・列数・非ゼロ要素数
Compression Ratio 問題サイズの縮小率を 1.0（元の大きさ）に対する比として表示

　

　

　3. [Progress]

　単体法の反復状況を表示するログです．

[Progress]
dual-phase2 start
    Iter.      Objective    Primal Inf.      Dual Inf.  Time(s)
        0  -1.209808e-03   4.129333e+02   0.000000e+00      0.0
      216   1.065989e-03   5.702500e+02   0.000000e+00      0.0
      444   1.272684e-03   5.780701e+02   0.000000e+00      0.0
      701   1.607672e-03   6.082018e+02   0.000000e+00      0.0
...

     8498   2.003588e+00   5.866762e-01   0.000000e+00      1.1
     8589   2.003588e+00   0.000000e+00   0.000000e+00      1.1
cleanup perturbation
     8589   2.000000e+00   0.000000e+00   0.000000e+00      1.1
undo preprocessing
primal-phase2 start
     8589   2.000000e+00   0.000000e+00   0.000000e+00      1.2

　各項目の意味は次の通りです．

項目 意味
Iter. 単体法の反復回数（iteration）
Objective 現在の目的関数値
Primal Inf. 主変数に対する実行不可能性の値（primal infeasibility）
Dual Inf. 双対変数に対する実行不可能性の値（dual infeasibility）
Time(s) 経過時間（秒）
Freedom （二次計画問題の場合のみ表示されます）基底解の自由度※

　

※ 自由度が大きいほど，解が実行可能領域（凸多面体）の頂点から離れ，その内部に位置していることを表します．

　

　ログの行間には，主に次のようなメッセージが表示されます．

メッセージ 意味
dual-phase1 start 双対単体法のフェーズ 1 を開始
dual-phase2 start 双対単体法のフェーズ 2 を開始
primal-phase1 start 主単体法のフェーズ 1 を開始
primal-phase2 start 主単体法のフェーズ 2 を開始
cleanup perturbation 収束性改善のために加えていた摂動（perturbation）を除去
switch to primal 主単体法への切り替え
switch to dual 双対単体法への切り替え
undo preprocessing スケーリングなどの前処理を元に戻す（ここでは presolve 以外の処理）

　

　

　4. [Postsolve]

　Presolve によって縮小した問題を元の問題に戻し，縮小後の問題で得られた解を元の問題の解へ復元する処理です．

[Postsolve]
undo presolve operations
primal-phase2 start
     8589   2.000000e+00   0.000000e+00   0.000000e+00      1.2

　復元後の解は，数値誤差の影響により最適解からずれる場合があります．そのため，復元した解を初期解として元の問題に対して単体法を実行します．通常，この反復はまったく行われないか，あるいはごく少ない反復数で終了します．

　

　5. [LP-Unfolding]

　LP folding によって折り畳んだ問題を元の問題に展開し，解を復元する処理です．

[LP-Unfolding]
unfold solution
constructing initial basis...
repairing initial basis...
dual-push
  Number of dual pushes required   : 418
  Now at iteration 1 out of 418
primal-push
  Number of primal pushes required : 2910
  Now at iteration 1 out of 2910
  ...
  Now at iteration 2875 out of 2910
primal-phase2 start
     8589   2.000000e+00   0.000000e+00   0.000000e+00      1.4

　ログの行間には次のようなメッセージが表示されます．

メッセージ 意味
unfold solution 折り畳まれた解を元の問題の解へ展開します
constructing initial basis... 展開後の解を基に元の問題の初期基底を構築します
repairing initial basis... 初期基底が数値的に不安定な場合に修正します
dual-push / primal-push 初期基底から最適基底へ到達するための push 操作を実行します
Number of dual / primal pushes required 必要な push 操作の総回数
Now at iteration X out of Y 必要な push 操作に対する進捗状況

　

　Postsolve と同様に，得られた解は数値誤差の影響により最適解からずれる場合があります．そのため，得られた解を初期解として元の問題に対して単体法を実行します．

2.3 単体法（simplex），有効制約法，クロスオーバーにおける出力
2.5 制約充足問題ソルバ（wcsp）における出力

 

 

上に戻る