具有定製成本函數的最小成本最大流算法

Question

什麼樣的成本函數可用於最小成本最大流算法？

是否有可能具有類似的成本函數：

• 如果在邊緣流是[1，X]，成本=固定成本+ C1 +流* cost_per_flow [C1]
• 如果之間流上的邊緣之間是[X + 1，Y]，成本=固定成本+ C2 +流* cost_per_flow〔C2〕
• 等

這是否以任何方式更改算法？

Answer 1

您可以合計固定成本，並將其從等式中移除。然後，將每條邊分成2條邊，每條邊都有適當的計算成本。

Answer 2

最小費用最大流算法僅僅是特定種類的線性節目的解算器。線性程序可以有效地解決的問題是凸性：在這種情況下，如果有兩個可行的流F和G，那麼對於[0，1]中的所有t，流tF +（1-t）G是可行的並且具有成本（F +（1-t）G）≤噸成本（F）+（1-t）成本（G）。對於你的目標，這基本上意味着在固定成本[1，X]是0，C1 ≤ C2，固定成本在[X + 1，Y]是（C1 - C2）X ≤ 0這看起來是這樣的：

6|  . 
5|  . 
4|  . 
3|  . 
2| . 
1| . 
0.---------- 
0 1 X 

或許這對你很重要的固定成本在[1，X> 0，但是這使得問題NP難問題。從圖中的斯坦納樹減少的是使每個邊的容量無限大，並且花費第一個單元的斯坦納樹問題指定的權重，其後爲0。使k-1 Steiner終端中的一個終端成爲容量爲k-1的源，其他終端以容量1下沉。請求最便宜的k-1個單位流。