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

バイナリー2 次計画問題(BQP)は,NP 困難な問題に含まれる組み合わせ最適化問題の1 つであり,マシンスケジューリング問題やCAD 問題に適用可能であるため,応用例が広い問題として知られている．本研究では,OR-Libraryにはない,大規模な問題を対象とする.このような大規模な問題に対する従来手法として,IGKLSが提案されており,その有効性が示されている.そこで本研究では,IGKLSを改良することにより,大規模な問題に対して更に効率よく解を探索することができるアルゴリズムを提案する.提案手法では,IGKLS の局所探索に変形k-opt局所探索法を組み入れることにより,局所探索の性能を高める.実験では10000変数の問題を用いて,従来のIGKLSと比較し,提案手法の有効性を示す.