尋找k-MST的整數LP形式化

Question

我正在尋找一個整數LP形式化的k-Minimum Spanning Tree problem。

我的想法：

• x_ij = 1表示有從i到j在樹的邊緣。
• Y_I = 1表示頂點i是樹的一部分
• c_ij是用於邊緣處的成本從i到j

目標函數：對於所有的i，J 分鐘總和（x_ij * c_ij）

約束：

1. 總和Y_I = K（1）
2. 總和（x_ij）對於所有j和某個i> =義（2）
3. 總和（x_ji）對於所有j和某個i> =義（3）
4. 2 * x_ij < =義+ YJ

（1）可確保恰好有在MST k個頂點。 （2）和（3）確保如果節點i在樹中，至少包含該節點的一條邊在樹中。 （4）說，如果樹和樹之間存在i和j之間的邊，那麼頂點i和j也必須在樹中。

不幸的是，這並不像預期的那樣工作。有誰知道我的錯誤？

Answer 1

您需要確保所選的子圖已連接。