algorithm - 寻找 k-MST 的整数 LP 形式化

Question

我正在为k-Minimum Spanning Tree 问题寻找整数 LP 形式化。

我的点子：

• x_ij = 1 表示树中有一条从 i 到 j 的边。
• y_i = 1 表示顶点 i 是树的一部分
• c_ij 是从 i 到 j 的边的成本

目标函数：所有 i,j 的 min sum(x_ij*c_ij)

约束：

1. 总和 y_i = k (1)
2. sum(x_ij) 对所有 j 和一些 i >= yi (2)
3. 所有 j 和一些 i >= yi (3) 的 sum(x_ji)
4. 2*x_ij <= yi+yj

(1) 确保 MST 中恰好有 k 个顶点。(2) 和 (3) 确保如果节点 i 在树中，则至少包含该节点的一条边在树中。(4) 表示如果树中 i 和 j 之间有一条边，那么顶点 i 和 j 也必须在树中。

不幸的是，这并没有按预期工作。有人知道我的错误吗？

Answer 1

您需要确保选择的子图是连接的。