NAGライブラリは大規模線形計画問題を解くための内点法ソルバー(e04mt)を提供しています。
線形計画問題は、その柔軟性とモデリングの容易さのおかげで、1940年代後半に最初の実用的なソルバーが開発されてすぐに非常に人気が出ました。それ以来、理論の大幅な改良と計算能力の向上により、物流や金融を含む多くの分野や業界で線形計画法は利用され、問題サイズも大幅に拡大しています。
e04mtは、シンプレックス/アクティブセット法に代わる実行可能な内部点法(IPM)に基づくソルバーです。過去20年間の活発な研究により、非常に効率的で信頼性の高いIPMが開発されてきました。アクティブセット法と比較して、このタイプのソルバーの主な特徴は、低い反復回数での高速収束ですが、各反復の計算コストは高くなります。内点法における一回の反復は、主に1つの大きな疎な線形システムを因数分解することで構成されています。
このソルバーは、非常に効率的なスパース線形代数パッケージに基づいて構築されており、実際には、内点法の2つのバリエーションであるPrimal -Dual法とSelf-Dual法を実装しています。Primal-Dualは通常、最速の収束を提供し、ソルバーのデフォルトの選択です。ただし、セルフデュアルには以下に示すような、いくつかの魅力的な性質があります。
- すべての収束測定値は同じ割合で減少
- 非常に信頼性の高い実行不可能性の検出
- 一般的に悪条件問題に対するより良い振る舞い
どちらの方法でも、e04nqなどのライブラリ内の他のソルバーと比較して、大規模問題で性能が大幅に改善されるはずです。
e04ncはNAG最適化モデリングスイートの一部であり、スイート内のソルバーのインターフェースの明確さと一貫性を提供します。