最適化セミナーのご案内

12.5 分枝限定法における出力

 混合整数計画問題を解く場合は,通常,自動的に分枝限定法が起動されます.その場合[Progress]で始まるセクションでの実行経過の出力は次のようになり,求解の進行状況を確認できます.

<iteration begin>
           .1.2B
    up:       1e+50 lo: 8.6617e+05 time:  0.1s:mem(MB)=0
                                      llen:1 #prob:10 #piv:210
#1  up:  9.0859e+05 lo: 8.6655e+05 gap: 42036 time:   1.6s:mem(MB)=2
                                       llen:359 #prob:1009 #piv:4223
#2  up:  9.0746e+05 lo: 8.6655e+05 gap: 40901 time:   6.6s:mem(MB)=4
                                       llen:1002#prob:2652 #piv:6493
#3  up:  9.0713e+05 lo: 8.6655e+05 gap: 40574 time:  12.4s:mem(MB)=8
                                      llen:1876 #prob:4776 #piv:9105
#4  up:  9.0692e+05 lo: 8.6655e+05 gap: 40361 time: 17.9s:mem(MB)=12
                                       llen:2756#prob:6896#piv:11802
                    (中略)
                                        llen:2680#prob:58708iv:65012
#47 up:  8.7972e+05 lo: 8.6655e+05 gap: 13161 time:174.4s:mem(MB)=43
                                      llen:2167#prob:59374 piv:65851
    up:  8.7972e+05 lo: 8.6655e+05 gap: 13161 time:180.1s:mem(MB)=43
                                       len:2169#prob:60990#piv:67529
#48 up:  8.7907e+05 lo: 8.6655e+05 gap: 12518 time:184.3s:mem(MB)=43
                                      llen:1470#prob:62102 piv:68561
#49 up:    8.79e+05 lo: 8.6655e+05 gap: 12446 time:190.4s:mem(MB)=43
                                      llen:1396#prob:64450#piv:71062
#50 up:  8.7843e+05 lo: 8.6655e+05 gap: 11876 time:192.2s:mem(MB)=43

 各行は,

  • 新しい暫定解が得られた
  • 所要メモリが50MB以上変動した
  • 60秒経過した

のいずれかの条件を満たせば出力されます.

 新しい暫定解が得られた場合は,行頭に"#"が表示されます."#"に続く番号は暫定解の番号です.それ以外の場合には#の項目がありません.

 他の項目の意味は次の通りです.

表示 意味
up 目的関数の上界値
lo 目的関数の下界値
gap 上下界ギャップ:(上界値 – 下界値)
time 経過時間(秒)
mem(MB) 全使用メモリ/実メモリ上にあるメモリ量
avail(MB) 現在実行している計算機で使用できるプロセスメモリ最大量/実メモリの残り最大量
llen 分枝限定法に対するリストの長さ
#prob 通算の子問題数
#pivot 通算のピボット数

 

 実行環境によっては"mem"の表示の「実メモリにあるメモリ量」を示す部分,および"avail"項は表示されません.

 この問題では合計50個の暫定解が求まり,最後の暫定解の上下界ギャップは11876であったことがわかります.

 単体法とともにwcsplpを用いた実行可能解探索の支援を用いる場合は,出力の中に下記のような出力が含まれます.

=== begin wcsp ===
# (hard/soft) = 0/918
# iteration = 24000
# time =  1.47 (s), succ = 1
=== end wcsp ===

 これはそれぞれ,以下の通りの意味をもちます.

  • (hard/soft): wcsplpが見つけた答えのhard penalty/soft penalty量
  • iteration: 求解に要した反復回数
  • time: 求解に要した時間
  • succ: 実行可能解が見つかった場合は1, 見つからなかった場合は0

 なお,wcsplpを用いた実行可能解探索の支援では,制約式や目的関数の係数が整数に丸められるため,hard penalty = 0でも実行可能解とは限りません.実行可能解が見つかったか否かは,succの値で判断します.


 

 

上に戻る