情報処理学会 第75回全国大会講演要旨

線形計画法が解く問題である線形計画問題は、線形等式、
または線形不等式で表された、目的関数と幾つかの制約条件で
構成されている最適化問題である。この問題は、規模によって
大きな実行時間がかかるため高速化手法を適応することが重要である。
そこで、線形計画法のライブラリの一つであるGLPKを解析したところ、
制約条件の係数行列中の0の占める割合や、値の分布によってプログラム中で
長い実行時間を占める部分が異なり、GPUの高速化対象とする計算や
その計算手法を変えた方が良いことがわかった。本論文では、
様々な係数行列に対するGLPKライブラリの挙動とそのGPUによる高速化への
影響を調査した。