需要一個算法來查找元素子集中的最小代價

我正試圖找到一個最優算法，可以找到最大的子集，其中元素的總和最低，同時覆蓋所有元素。需要一個算法來查找元素子集中的最小代價

例如： - 想象一下A B C是零售商，W X Y Z是產品，目標是儘量減少訪問次數，降低價格。

A B C 
W 4 9 2 
X 1 3 4 
Y 9 3 9 
Z 7 1 1 

So it appears my top two choices are 
a) B:{XYZ} - 7 C:{W} - 2 
b) C:{WXZ} - 7 B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9.

這個問題看起來類似於頂點覆蓋和其他線性規劃算法，但我找不出合適的。

更新：

看來我需要添加一個額外的變量。介紹t。如果訪問最少的零售商和最少的零售商的成本> t，則選擇下一個前者。

Continuing with the example. 

say t = 5, 

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7 C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7 C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7 C:{W} - 2 is picked

真的，我只是有興趣，如果已經有一個適合這種模式的算法。我不能成爲需要這種優化的第一人。

來源

2013-06-26 Sushant Rao

Hrmm，考慮使用樹，也許深度優先搜索？過了一段時間，因爲我做了這樣的事情，似乎它可以工作。 – Trent

什麼是最小化價格和最小化訪問之間的折中。您是否想以最低的價格找到滿足這些要求的最低訪問次數？ – Owen

這個問題看起來像http://en.wikipedia.org/wiki/Transportation_theory_(mathematics） – MBo

您有兩個目標的問題 - 1.最大限度地降低產品的總成本，並最小化訪問的商店數量。（@ btilly的評論正確地顯示了兩種競爭解決方案。）

多種目標在這些類型的Integer編程問題中相當常見。 See MCDM。要解決這個問題，你需要有類型的成本（您目前只有一個。）

從零售商[R購買產品p（你已指定）C_rp
的成本費用參觀零售商：C_r

直覺：如果C_r非常高，那麼我們會從一個零售商購買所有產品。如果C_r很小，那麼我們會去多家零售商，並從最便宜的人那裏購買。

您的問題可以建模爲「Assignment Problem」的變體。另外，如果您需要更多參考資料，請閱讀所謂的fixed-charge transportation problems（FCTP）。（有一個固定收費來訪問零售商一次。）

所以到整數規劃：

決策變量

Binary 
    X_rp = if product p is purchased from retailer r, 0 otherwise 
    Y_r = 1 if retailer r is visited, 0 otherwise

目標函數

Min C_rp X_rp + C_r Y_r

限制條件

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer)

接下來，我們需要確保Y_r是1，即使其中一個X_rp對於那個零售商來說也是1。通常情況下，我們會採用Big M方法，但在這個問題上更容易。

X_rp <= Y_r for all p, for all r.

如果任何一個變量x變爲1，迫使Y_r成爲1.該模型將爲此付出代價C_r。

要解決，您可以使用任何LP解算器。好消息是該問題具有完整性屬性，這意味着即使在使用線性編程解決方案技術時，整數解決方案也自然會出現。

希望有所幫助。

來源

2013-06-26 18:22:13

非常感謝。它有很多幫助。 –

賦值問題確實有一個完全單模LP，但是帶有新約束的LP不是TU，考慮到從集合掩護存在一個保留客觀的約簡存在，這並不奇怪。 –

我會將這個問題稱爲非度量設施位置。我同意你選擇整數編程作爲解決方法。 –

需要一個算法來查找元素子集中的最小代價

回答

相關問題