最小費用流積分定理

Question

最小費用流問題的完整性定理指出，給定「積分數據」，對於與最小費用流相對應的問題，總是有一個整體解決方案。整體數據的概念對我來說有點混亂，因爲大多數論文和教程都指出，需求，供應和能力應該是不可或缺的。現在，一個容量約束通常被表示爲

l_i <= c_i <= u_i 

其中l_i是下界邊緣i的容量，並且u_i是上限。爲了保持完整性定理，l_i and u_i是不是整數？這個疑問來自這樣的事實，這並不一定意味着流量本身總是整數，例如，對於l_i = 0, u_i = 1，邊緣i可以具有0.5的流量。

Answer 1

是的，這正是完整性定理所說的。

如果所有l_i和u_i的是整數，並且任何可行的解決方案存在，那麼必須存在一個解決方案，其中所有流都是整數。

這並不意味着所有解決方案都必須是整數。只要至少有一個會。