厳密解法

👉 数理最適化セミナー開催中！！

• 読み: げんみつかいほう

• 英名:

最適化問題に対して，最適性の保証された解（厳密解）を求める解法のこと． 主に NP 困難な問題に対して用いられる． 例えば，混合整数計画問題に対する分枝限定法，分枝価格法などがある．

従来 NP 困難な問題に対して，厳密解法ではなく近似解法を用いることが多かった． しかしながら，近年計算機環境・アルゴリズムの発展により，現実的な時間内で厳密解を得ることが可能になってきている． 例えば，巡回セールスマン問題は従来においては近似解法の研究が盛んであったが， 近年では厳密解法によって大規模巡回セールスマン問題を解く試みが行われおり成功をおさめている [1]．

関連

• NP 困難

• 近似解法

参考文献

[1]

David L Applegate, Robert E Bixby, Vašek Chvatál, and William J Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006. ISBN 9780691129938. URL: http://www.jstor.org/stable/j.ctt7s8xg.