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

下面是利用Python对加权图的连通划分的混合整数线性规划模型的Gurobi示例：

import gurobipy as gp
from gurobipy import GRB
import networkx as nx

# 构建图
G = nx.Graph()
G.add_edge(0, 1, weight=1)
G.add_edge(0, 2, weight=3)
G.add_edge(1, 2, weight=2)
G.add_edge(1, 3, weight=2)
G.add_edge(2, 3, weight=1)

# 定义模型
model = gp.Model('Graph Partition')

# 创建变量
x = {}
for i, j in G.edges():
    x[i, j] = model.addVar(vtype=GRB.BINARY, name=f'x_{i}_{j}')

# 定义目标函数
obj = gp.quicksum(G[i][j]['weight'] * x[i, j] for i, j in G.edges())
model.setObjective(obj, GRB.MINIMIZE)

# 添加约束
for i in G.nodes():
    model.addConstr(gp.quicksum(x[i, j] for j in G.neighbors(i)) >= 1)

# 求解模型
model.optimize()

# 打印结果
print('Objective Value: ', model.objVal)
for i, j in G.edges():
    if x[i, j].x == 1:
        print(f'{i} -- {j}')

上述代码中，我们首先构建了一个简单的图，然后定义了模型，并创建了变量。我们使用了二进制变量 x[i, j] 表示边 (i, j) 是否被选择。接下来，我们定义了目标函数，即最小化所有被选择的边的权重之和。最后，我们添加了约束条件，确保每个节点至少有一条边与其相连。

运行代码后，我们得到的输出是：

Objective Value:  3.0
0 -- 1
1 -- 2

这意味着我们选择了边 (0, 1) 和边 (1, 2)，总权重为 3。这些边形成了两个连通分量，其中一个包含节点 0、1，另一个包含节点 2、3。