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

Question

我正在寻找 k-Minimum Spanning Tree problem 的整数 LP 形式化.

我的想法:

• 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. 对所有 j 和一些 i >= yi (2) 求和(x_ij)
3. 对所有 j 和一些 i >= yi (3) 求和(x_ji)
4. 2*x_ij <= yi+yj

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

不幸的是，这并没有像预期的那样工作。有谁知道我的错误吗？

Answer 1

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