加快單純形法

我玩弄一個巨大的單純形法我已經在這裏找到：https://github.com/JWally/jsLPSolver/加快單純形法

我創造，我已經建立了一個模型，我使用上面的算法解決問題的jsfiddle。 http://jsfiddle.net/Guill84/qds73u0f/

該模型基本上是一個很長的變量和約束數組。你可以把它想象成試圖在不同的樞紐（國家）之間找到最便宜的旅客運輸方式，其中每個國家都有最低的乘客需求，最大的乘客量，並且每個連接都有一個價格。我不在乎乘客去哪裏，我只想找到最便宜的方式來分發他們。要做到這一點我用下面的最小化目標：

model = { 
     "optimize": "cost", 
      "opType": "min", 
      "constraints": { \\etc...

我很高興與模型和算法提供的答案......但後者需要很長的時間來運行（>了15秒。）有什麼方法可以加快計算速度？

親切的問候和謝謝。 G.

來源

2015-04-02 Noobster

想通了。代碼中最昂貴的部分是旋轉操作;事實證明，通過增加0來更新矩陣做了很多工作。預先做了一點邏輯，以防止這種情況將節點上的運行時間從約12秒降低到約0.5秒。

for (i = 0; i < length; i++) { 
     if (i !== row) { 
      pivot_row = tbl[i][col]; 
      for (j = 0; j < width; j++) { 


       // No point in doing math if you're just adding 
       // Zero to the thing 


       if (pivot_row !== 0 && tbl[row][j] !== 0) { 
        tbl[i][j] += -pivot_row * tbl[row][j]; 
       } 
      } 
     } 
    }

來源

2015-04-14 22:18:52 JWally

賈斯汀，這真是令人印象深刻。我非常希望有一天我們能夠一起工作，我非常樂意向您學習。 – Noobster 2015-04-15 18:52:48

這聽起來好像你有一個minimum-cost flow problem。 Zealint提供了一個合理的TopCoder tutorial on min-cost flow，他涵蓋了循環消除算法，這是我的第一個建議（假設沒有可以爲您的LP求解器完成的快速優化）。如果這還太慢，那裏就有一些文獻。

由於您決定用LP求解器解決這個問題，我的建議是編寫一個更簡單的求解器，該求解器快速且貪婪但並不理想，並將LP用作LP的出發點與出發點的差異。

來源

2015-04-02 13:27:20

大衛你好！是的，這確實是最低成本流量問題。我並不是試圖重新發明輪子或從頭開始寫算法。事實上，我不知道如何開始，這就是爲什麼我使用上面的單純。我喜歡它，因爲我可以將它作爲一個數組直接提供給我的變量和約束。爲什麼它需要這麼長時間才能完成？作爲一個起點，我想在考慮其他選項之前，先對上述內容進行研究。 – Noobster 2015-04-02 15:59:25

@Noobster你正在使用的LP解算器是一個玩具，但它看着它，我看不到任何明顯的性能問題。我將我的建議編輯爲答案。 – 2015-04-02 16:18:12

@Noobster，我很高興除了我以外的其他人正在使用我的單純圖書館。我經歷了一遍，看了看它，並且正在繞過與你相同的運行時間（10-20秒）。有一段代碼不必要地將數組轉換爲2d數組中的1d數組。伴隨着你的問題，每當它發生的時候，性能就會消耗60ms（對於你的問題，137次）。

我已經在回購中糾正了這一情況，並且看到運行時間約爲2秒。可能有大量的代碼需要清理優化，但是我爲此構建的問題集（http://mathfood.com）太小，我從來不知道這是一個問題。謝謝！

對於它的價值，我將單純的算法從大學教科書中拿出來，並將其轉化爲代碼; MILP片段來自維基百科。

來源

2015-04-02 18:08:37 JWally

加快單純形法

回答

相關問題