大規模マルチコンポーネント混合選択問題に対する厳密解法のGPUによる高速化

摘要

直一並列システムの信頼性を最適化する問題は多次元非線形ナップザック問題として定式化できる．この問題に対しては，動的計画法に基づくアルゴリズムが数々提案されてきた．本論文では，多次元 非線形ナップザック問題に対する動的計画法アルゴリズムをGPUを用いて高速化する手法を提案する．既存の厳密解法では計算困難な規模のシステム信頼性最適化問題に対して提案手法を適用し，実用的な時間内で厳密解が得られることを示す．