組合優化與相互依存的變量

這是我在這些論壇上的第一篇文章，在此先感謝所有回覆。組合優化與相互依存的變量

我正在開發一個java應用程序，其中我遇到了我認爲被稱爲「組合優化問題」的內容。我只有基本的數學技能，所以試圖調查這樣一個問題的設置迄今尚未取得豐碩成果。

基本上，我想要做的是編程找到變量v1，v2，v3等更大集合N的最優子集n的最有效方法。變量都有一個確定的值/分數到取決於可能包括或不包含在子集中的某些其他變量的值/分數。

我有興趣選擇給出最大總值/分數的子集。

因此，例如，全組N個由以下變量的，並具有以下確定值以及關係到其它變量：

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 }

有一個相對於一種或多種其它選擇的可變意味着總價值將有一定的「起飛」 - 爲了這個例子，讓我們說每個關係的一個。因此在選擇前五個變量作爲一個子集將給予30，總價值：

v1 8 { v2 ; v8 }  = 8 - 1 = 7 
v2 6 { v1 ; v4 }  = 6 - 2 = 4 
v3 9 { }    = 9 - 0 = 9 
v4 7 { v2 ; v5 ; v8 } = 7 - 2 = 5 
v5 6 { v4 ; v10 }  = 6 - 1 = 5

這當然不是這樣的小套的問題，但我目前面臨的套10K的100K和子集 - 用目前的算法，我的電腦在3天內計算出瞭解決方案！

我不一定需要解決這個問題的代碼，而是最好的數學方法來做到這一點（如果有的話）！請記住，我很難理解高於基本水平的數學符號。

再次，在此先感謝所有回覆！

來源

2016-12-20 Einar Jakob Hovland

不幸的是，這個問題很難找到最佳解決方案。

如果你能有效地解決這個問題，那麼你可以通過爲每個頂點的值設置爲1解決NP難maximum independent set problem，和一個非常大的懲罰每個邊緣。

所以，你應該尋找近似的解決方案。您可能會發現通過模擬退火或遺傳算法可以得到合理的答案。

來源

2016-12-20 13:26:43

花了我相當一段時間，但我現在試圖掌握在這裏提到的幾個解決方案。我最終結束了模擬退火。不知道這是否是正確的/最佳的解決方案，但至少它很容易理解和實施 - 而且它似乎表現得相當不錯。感謝所有的建議！ –

你可以看到你的設置爲圖形。每個vX是具有相應值的節點/頂點。例子v1是一個值爲8的節點/頂點，v2是一個具有值6的節點/頂點，等等。然後它們之間有邊緣。示例v1有兩個邊：一個用於v2，另一個用於v8。每條邊也可以有一個值（在你的情況-1）。所以如果你使用圖形，並選擇v1到v5：你有8 + 6 + 9 + 7 + 6（頂點值）-1 -1 -1 -1 -1 -1（邊緣值）。

試試看這http://jgrapht.org/，看看它是否可以幫助你。

另請參見Graph Teory：http://www.people.vcu.edu/~gasmerom/MAT131/graphs.html。觀察最長/最短路徑算法（例如：http://www.maxburstein.com/blog/introduction-to-graph-theory-finding-shortest-path/）

來源

2016-12-20 12:17:43 pringi

線性程序解算器，以輸入像

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 }

並將其轉換爲一個整數程序像

maximize 8*v1 - v1v2 - v1v8 
     + 6*v2 - v2v1 - v2v4 
     + 9*v3 
     + 7*v4 - v4v2 - v4v5 - v4v8 
     + 6*v5 - v5v4 - v5v10 
     + 8*v6 - v6v7 
     + 5*v7 - v7v6 
     + 9*v8 - v8v1 - v8v4 
     + 6*v9 
     + 7*v10 - v10v5 

subject to 
v1 + v2 - v1v2 <= 1 
v1 + v8 - v1v8 <= 1 
v2 + v1 - v2v1 <= 1 
v2 + v4 - v2v4 <= 1 
v4 + v2 - v4v2 <= 1 
v4 + v5 - v4v5 <= 1 
v4 + v8 - v4v8 <= 1 
v5 + v4 - v5v4 <= 1 
v5 + v10 - v5v10 <= 1 
v6 + v7 - v6v7 <= 1 
v7 + v6 - v7v6 <= 1 
v8 + v1 - v8v1 <= 1 
v8 + v4 - v8v4 <= 1 
v10 + v5 - v10v5 <= 1 

binary v1, v1v2, v1v8, 
     v2, v2v1, v2v4, 
     v3, 
     v4, v4v2, v4v5, v4v8, 
     v5, v5v4, v5v10, 
     v6, v6v7, 
     v7, v7v6, 
     v8, v8v1, v8v4, 
     v9, 
     v10, v10v5

您的實例大小可能太多了最佳的解決方案，但一從來不知道...

來源

2016-12-20 17:35:33

組合優化與相互依存的變量

回答

相關問題