我正在寻找k-Minimum Spanning Tree problem的整数lp形式化。
我的想法：
x_i j=1表示树中有一条从i到j的边。
y_i=1表示顶点i是树的一部分
c_i j是从i到j的边缘的成本
目标函数：
所有i，j的最小和（x_ij*c_ij）
限制条件：
和y_i=k（1）
所有j和一些i>=yi（2）的和（x_ij）
所有j和一些i>=yi的和（x_ji）（3）
2*xúij（1）确保MST中正好有k个顶点（2）和（3）确保如果节点i在树中，则包含该节点的至少一条边在树中（4）如果树中的i和j之间有一条边，那么顶点i和j也必须在树中。
不幸的是，这并不像预期的那样有效有人知道我的错误吗？
最佳答案
您需要确保所选子图已连接。