B.2.4 並列分枝限定法
並列分枝限定法では「Supervisor」および「Worker」と呼ばれる役割が協調して処理を行います[17]．Supervisorは並列化動作を統制し，Workerは与えられたタスクを処理します．
Nuorium Optimizerは次の3つの並列分枝限定法を提供しています．
- Racing（デフォルト）
- Deterministic Racing
- Subtree
RacingとSubtreeは[18]を参考にしています．
- Racing
- Racingは複数のWorkerが同一の整数計画問題を並行して解く手法です．各Workerでは異なる求解オプションが設定されています．同一の問題を解くため，冗長な計算を多く含みますが，デフォルトの求解オプションでは発見することが容易でない解を得ることができます．短時間で優良な解を得ることが重視される場合に有効な手法です．非決定性並列処理のため，同じ計算環境かつ同じ入力データであっても，異なる計算プロセスを経る可能性があります．
- Deterministic Racing
- Deterministic RacingはRacingに決定性を持たせた手法です．ここで言う決定性とは，同じ計算環境かつ同じ入力データであれば同じ結果が得られる（同じ計算プロセスを経る）ことを意味します．
デバッグやテストがしやすく，システムの計算エンジンとして利用するなど，より安定的に利用したい場合に有効です．注意点として決定性を持たせている分計算性能が犠牲になっているため，問題によっては通常の分枝限定法よりも遅くなるケースがあります．また，計算性能はスレッド数を多くするほど悪化する可能性があるため，適切なスレッド数を事前に調べておくことが重要です． - Subtree
- Subtreeは並列に分枝木を探索する手法です．Racingと比べると探索の効率が良く，小から中規模の問題で最適解が必要となる場合に有効です．注意点として大規模な問題（特に分枝限定法の前処理や単体法に時間がかかる問題）を本手法で解かせると，他のWorkerに探索させる分枝木のルート問題の生成に時間がかかるため，通常の分枝限定法よりも遅くなる可能性があります．このような問題の場合はSubtreeよりもRacingが推奨されます．
並列分枝限定法を実行する際の求解オプションについては「整数計画法（simplex/asqp）に有効な求解オプション」の項に解説があります．
上に戻る