線型計画法
しかしカチヤンのアルゴリズムの実用性は期待はずれで、一般にシンプレックス法の方が効率的である。このアルゴリズムの主な重要性は、アルゴリズムの多項式性を示す証明手段を提供した事と、内点法の研究を促進したことにある。実行可能領域の辺のみを探索するシンプレックス法に対し、内点法は実行可能領域の内部を動くアルゴリズムとなっている。
1984年にナレンドラ・カーマーカーはカーマーカー法(射影変換法)を提案した。この方法は理論上でも実際でもいい結果の得られる最初のアルゴリズムで、最悪の場合でも多項式時間で解くことができ、実際の問題ではシンプレックス法と比べてかなり効率的に解くことができることが示されている。それ以降は多くの内点法が提案されて研究されている。よく使われる内点法にはMehrotraの予測子・修正子法と小島・水野・吉瀬の主双対内点法がある。
すぐれた実装のシンプレックス法と内点法の効率は、線型計画法の応用としてはっきりした優劣は無いというのが現在の見解である。しかしながら、目的関数や右辺項が僅かに変動した問題の最適化を繰り返し行う際は、シンプレックス法が優れている。
LPのソルバーは、輸送におけるネットワークフロー問題(線型計画問題として定式化できる)のような産業のさまざまな問題の最適化のために広く普及している。