# 解決線性程序的最新算法

Průša and Werner（2019）表明，一般的線性規劃問題在幾乎線性的時間內減少了許多經典NP硬問題的LP鬆弛（假設實例的稀疏編碼）。正如作者所寫：

Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.

Průša和Werner的結果表明，無論基礎公式有多好（或有效不等式有多好），我們仍然需要有效地求解得到的線性程序（即ANY線性程序），以便能夠解決大問題。

The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.

The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's the implementation challenges, i.e., manipulating matrices that take up massive memory (and sometimes need to be cached into the hard drive or distributed among numerous machines), as well as numerical stability and factorising the coefficient matrix which are prone to large scale difficulties.

You are right that the dual simplex (and to some degree the primal simplex) are still very much state-of-the-art ways to solve LPs. The last 3 decades saw significant improvements on these algorithms but their main advantage remains warmstarting capabilities. Inside MILP solvers we need to solve many closely related problems and dual simplex (and in some cases primal simplex) excel at doing that.

The interior point method lacks warmstarting but has the major advantage that for large problems it can be threaded fairly efficiently. Simplex algorithms in most cases gain very little from using parallel computing, which in the MIP solver setting is not that much of a problem.

"New" methods for solving LPs I am aware of (and currently remember) are the following: