トップ > 数理計画用語集 > 厳密解法

数理計画用語集

厳密解法

読み:げんみつかいほう
関連NP 困難近似解法

最適化問題に対して,最適性の保証された解(厳密解)を求める解法のこと.主に NP 困難な問題に対して用いられる.例えば,混合整数計画問題に対する分枝限定法,分枝価格法などがある.従来 NP 困難な問題に対して,厳密解法ではなく近似解法を用いることが多かった.しかしながら,近年計算機環境・アルゴリズムの発展により,現実的な時間内で厳密解を得ることが可能になってきている.例えば,巡回セールスマン問題は従来においては近似解法の研究が盛んであったが,近年では厳密解法によって大規模巡回セールスマン問題を解く試みが行われおり成功をおさめている[1].

[参考]
[1] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton Univ Pr, 2007