尋找一個基於模板的C++庫，可以解決線性程序

-2

我正在尋找一個LP（線性規劃）求解器，它使用Simplex算法或任何它喜歡的。我還有一個額外的要求，解決者將執行所有的計算，而不會有任何精度損失！所以如果我能找到一個基於模板的C++庫，那讓我定義它使用的數值變量的下劃線類型，我會讓它使用boost的類型cpp_ratinal，因此所有的計算都不會損失任何精度由於浮點四捨五入。尋找一個基於模板的C++庫，可以解決線性程序

這樣的C++庫是否存在？

來源

2014-08-29 Moti

你的意思是cpp_rational？ – Jiminion 2014-08-29 17:23:21

是的，cpp_rational。 – Moti 2014-08-29 17:57:12

-1

在SoPlex看一看：

http://soplex.zib.de

SoPlex採用了一種名爲「迭代優化」以提高解決方案的質量，以任意精度的技術。所有的單工操作均以雙精度算法執行，以在短時間內獲得接近最優的解決方案。之後，稍微修改（減少誤差）的LP上執行很少的樞軸以確定確切的解決方案。它以模板方式使用GMP，Gnu多精度庫 - 如果您不喜歡GMP，也可以使用cpp_rational。在目前的發行版本中，LU分解還不能用於精確算術，因此您無法獲得確切的最優性證明。這已經在我們的開發者版本中實現了，但將在今年年底發佈。

http://opus4.kobv.de/opus4-zib/solrsearch/index/search/searchtype/collection/id/16090/start/0/rows/10/subjectfq/Exact+linear+programming

來源

2014-08-30 09:25:50 mattmilten

我認爲* QSOpt有一個選項可以做類似的事情。 – tmyklebu 2014-08-30 09:28:58

另外，SoPlex如何處理車輪完全脫落的情況---基礎因式分解對解決以左手邊爲基礎的方程式沒有任何幫助？似乎迭代改進不能幫助你。 – tmyklebu 2014-08-30 09:36:19

你是什麼意思的基礎是左側？如果因子分解是在有理算術中完成的，並且基矩陣是真正的非奇異的，則可以求解線性方程組 - 無論左（或右）手的樣子如何。由於依然存在許多依賴於浮點運算的操作，因此可能仍會發生單純形算法崩潰。 – mattmilten 2014-08-31 20:02:46

兩個SoPlex和QSOpt有確切單純求解。他們的表現會比你打算做的更好。然而，我應該警告你，SoPlex的確切的單純形求解器並不實際工作;使用SoPlex報告不可行性的理性數據構建可行的線性程序非常簡單。

對整個求解過程使用精確算術並不是一個好主意。你需要用精確的算術來排列大矩陣，並且涉及的確切數量會變得很大。我相信GLPK的確切求解器在有理算術中運行單純形式;你可以玩它，看看你有多喜歡它的表現。

在內點求解器中，SDPA-GMP是使用任意精度算法的線性規劃泛化的內點方法。您必須決定要使用的精度，但是您可以使用SDPA-GMP獲得非常高精度的解決方案，然後進行某種高精度分頻以獲得精確的最佳解決方案。（我從來沒有試過這個，因爲我從來沒有想要完全解決LP問題。）我會懷疑在這種情況下基於Simplex的求解器運行速度比IPM快。

來源

2014-08-30 09:34:35 tmyklebu

尋找一個基於模板的C++庫，可以解決線性程序

回答

相關問題