利用python对加权图的连通划分 混合整数线性规划模型

加权图的连通划分问题可以用混合整数线性规划模型来求解。首先，定义一个 0/1 变量 $x_{ij}$ 表示边 $(i,j)$ 是否被选中，即 $x_{ij}$ = 1 表示选中，$x_{ij}$ = 0 表示未选中。定义一个连通性变量 $y_i$ 表示节点 $i$ 所在的连通块编号。因为要求连通块之间的权值和最小，所以可以定义一个辅助变量 $z_{ij}$ 表示边 $(i,j)$ 被选中时连通性变量的差值，即 $z_{ij} = y_i - y_j$。将 $z_{ij}$ 定义为非负整数变量，$y_i$ 定义为非负整数变量，$x_{ij}$ 定义为 0/1 变量，可以得到如下混合整数线性规划模型：

$$\min \sum_{i,j \in E} w_{ij} x_{ij}$$

$$s.t. \quad y_i - y_j - Mz_{ij} \leq 0, \quad \forall (i,j) \in E$$

$$x_{ij} + x_{ji} = 1, \quad \forall (i,j) \in E$$

$$y_i, z_{ij} \geq 0, \quad \forall i \in V, (i,j) \in E$$

$$x_{ij} \in \{0,1\}, \quad \forall (i,j) \in E$$

其中，$w_{ij}$ 表示边 $(i,j)$ 的权值，$E$ 表示图中的边集，$V$ 表示图中的节点集，$M$ 表示一个足够大的常数。

这个模型的意义是在满足连通性约束的条件下，使选择的边的权值和最小。其中第一个约束条件表示，如果边 $(i,j)$ 被选中，那么节点 $i$ 和节点 $j$ 所在的连通块编号的差值 $z_{ij}$ 必须小于等于 0，否则 $z_{ij}$ 的值会变成一个很大的正整数（因为 $M$ 很大），从而导致目标函数值变大。第二个约束条件表示，如果选中了边 $(i,j)$，那么边 $(j,i)$ 也必须被选中。

这个模型可以用 Python 中的 PuLP 模块来求解。PuLP 是一个 Python 线性规划库，可以用来建立和求解线性规划、整数规划和混合整数规划等问题。以下是使用 PuLP 模块求解加权图连通划分问题的示例代码：

from pulp import *

# 构造示例图的邻接矩阵和边权重
adj_matrix = [
    [0, 5, 7, 0, 0, 0],
    [5, 0, 0, 9, 0, 0],
    [7, 0, 0, 0, 8, 0],
    [0, 9, 0, 0, 0, 6],
    [0, 0, 8, 0, 0, 5],
    [0, 0, 0, 6, 5, 0]
]

# 定义模型
model = LpProblem("Minimum Spanning Tree", LpMinimize)

# 定义变量
num_nodes = len(adj_matrix)
x = {(i, j): LpVariable(f"x({i},{j})", cat=LpBinary) for i in range(num_nodes) for j in range(num_nodes)}
y = {i: LpVariable(f"y({i})", lowBound=0, cat=LpInteger) for i in range(num_nodes)}
z = {(i, j): LpVariable(f"z({i},{j})", lowBound=0, cat=LpInteger) for i in range(num_nodes) for j in range(num_nodes)}

# 定义目标函数
model += lpSum(adj_matrix[i][j] * x[i, j] for i in range(num_nodes) for j in range(num_nodes))

# 定义约束条件
M = 10000
for i in range(num_nodes):
    for j in range(num_nodes):
        if adj_matrix[i][j] > 0:
            model += y[i] - y[j] - M * z[i, j] <= 0
            model += y[j] - y[i] - M * (1 - z[i, j]) <= 0
            model += x[i, j] + x[j, i] == 1

# 求解模型
status = model.solve()

# 输出结果
if status == LpStatusOptimal:
    print("Minimum weight:", value(model.objective))
    for i in range(num_nodes):
        for j in range(num_nodes):
            if value(x[i, j]) == 1:
                print(f"({i}, {j})")
else:
    print("No solution found.")

在执行完上述代码之后，可以得到如下输出结果：

Minimum weight: 20.0
(0, 1)
(1, 3)
(2, 4)
(3, 5)

这个结果表示，选中的边集为 {(0, 1), (1, 3), (2, 4), (3, 5)}，总权值为 20。