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

2.5 制約充足問題ソルバ（wcsp）における出力

　制約充足問題ソルバ（wcsp）を用いた場合には，[Progress]で始まるセクションに進捗が表示されます．

　まず，<preprocess begin>から<preprocess end>ではwcsp実行前の準備がおこなわれます．非常に大規模な問題でない限り，ここに要する時間は僅かです． 

<preprocess begin>..........<preprocess end>
preprocessing time: 0.000465(s)

　次に，<iteration begin>から<iteration end>ではwcsp実行の進捗が表示されます．ここでは，最良解におけるハード制約のペナルティ，セミハード制約のペナルティ，ソフト制約のペナルティと最良解を見つけたときの時間及び反復回数が逐次表示されます．問題にセミハード制約が存在しない場合，セミハード制約のペナルティは表示されません．また，最良解を更新していない場合は表示が更新されませんが，計算は行われています．試行回数(TryCount)が2以上の場合は試行回数分の進捗表示が行われます．また，wcspで並列化オプションを有効にした場合はメインスレッドの進捗のみ表示されます．以下は進捗表示の一例です． 

<iteration begin>
--- TryCount = 1 ---
# random seed = 1
(hard/semihard/soft) penalty= 45/12/4807, time= 0.00(s)
<greedyupdate begin>...........<greedyupdate end>
greedyupdate time= 0.00066(s)
(hard/semihard/soft) penalty= 0/8/3157, time= 0.00(s), iteration= 1
(hard/semihard/soft) penalty= 0/6/2905, time= 0.00(s), iteration= 2
(hard/semihard/soft) penalty= 0/6/2831, time= 0.00(s), iteration= 3
(hard/semihard/soft) penalty= 0/6/2783, time= 0.00(s), iteration= 4
(hard/semihard/soft) penalty= 0/6/2746, time= 0.00(s), iteration= 5
(hard/semihard/soft) penalty= 0/4/2775, time= 0.00(s), iteration= 8
(hard/semihard/soft) penalty= 0/2/3320, time= 0.00(s), iteration= 14
(hard/semihard/soft) penalty= 0/2/3283, time= 0.00(s), iteration= 15
(hard/semihard/soft) penalty= 0/0/4746, time= 0.00(s), iteration= 254
--- End Phase-I iteration ---
(hard/semihard/soft) penalty= 0/0/4094, time= 0.01(s), iteration= 368
# (hard/semihard/soft) penalty= 0/0/4094
# time = 0.01/0.02(s)
# iteration = 368/1000
<iteration end>

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

項目 意味
TryCount 現在の試行回数
random seed 使用した乱数の種
greedyupdate time 貪欲法によって初期解を更新するのにかかった時間
(hard/semihard/soft) penalty ハード，セミハード，ソフト制約のペナルティ量
time 経過した時間
iteration 反復回数
End Phase-I iteration ハード制約とセミハード制約が0になったことを意味する
time = X/Y(s) 最良解の発見にX秒，wcspの計算開始から終了までにY秒かかったことを意味する
iteration = X/Y 最良解の発見にX回，wcspの計算開始から終了までにY回反復したことを意味する

　

　TryCountが2以上の場合は乱数の種を変えて複数回計算が行われます．全試行が終了した後にサマリが表示されます．以下はサマリの一例です．

<summary>
 trycount         hard     semihard         soft    iteration  time(s)
        1            0            0         2284         9796     0.49
        2            0            0         2160         5969     0.32
        3            0            0         2370         9760     0.50
        4            0            0         2298         4029     0.21
        5            0            0         2420         9326     0.46
        6            0            0         2422         3382     0.18
        7            0            0         2297         9574     0.47
*       8            0            0         2119         7698     0.39

　

　サマリの内容は各試行における最良解のハード，セミハード，ソフト制約のペナルティ量と最良解を見つけるのにかかった時間及び反復回数です．"*"は全試行の中で最も良い解を表します．この例の場合，8回目の試行で得られた解が最も良いことを意味します．

　計算終了後，[Result]セクションに求解結果が出力されます．wcsp特有の項目は次の通りです．

項目 意味
STATUS 求解ステータス．正常終了した場合はNORMAL, 異常終了した場合はERRORが出力されます．
TERMINATE_REASON wcspの計算が終了した理由
PENALTY 総ペナルティ量．ハード，セミハード，ソフト制約のペナルティ量の総和が出力されます．
RANDOM_SEED 最良解を見つけた乱数の種
2.4 単体法（hsimplex）における出力
2.6 分枝限定法における出力

 

 

上に戻る