解決線性程序的最新算法


14

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.

線性編程是解決整數線性程序(通過基於LP的分支定界方法)的重要工具。解決這種整數程序已經取得了巨大的進步。但是,在解決一般的線性規劃問題上似乎沒有太多進展。據我所知,現代IP求解器仍使用經典的單純形算法或其對偶變體(甚至作為默認的LP算法)。

是否有任何新算法在實踐中(至少在平均水平上)有可能擊敗單純形算法?如果沒有,那我想知道為什麼嗎?

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

8

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.


3

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: