0,1整数规划求解最小顶点覆盖问题代码

以下是使用 PuLP 库对最小顶点覆盖问题进行 0-1 整数规划求解的 Python 代码：

from pulp import *

# 构建数据
n = 5  # 点数
m = 7  # 边数
edges = [(1,2), (1,4), (2,3), (2,5), (3,4), (4,5), (5,1)]

# 创建问题
prob = LpProblem("Minimum Vertex Cover Problem", LpMinimize)

# 创建决策变量
x = LpVariable.dicts("x", range(1, n+1), 0, 1, LpInteger)

# 创建目标函数
prob += lpSum([x[i] for i in range(1, n+1)])

# 创建约束条件
for (i, j) in edges:
    prob += x[i] + x[j] >= 1

# 求解问题
prob.solve()

# 输出结果
print("Status:", LpStatus[prob.status])
print("Minimum Vertex Cover:")
for i in range(1, n+1):
    if value(x[i]) > 0.5:
        print(i, end=" ")

其中，`n` 和 `m` 分别表示点数和边数，`edges` 存储边的信息。`LpProblem` 函数用于创建问题，`LpVariable` 用于创建决策变量，`lpSum` 用于创建目标函数，`prob +=` 用于添加约束条件。

在求解问题后，使用 `LpStatus[prob.status]` 获取求解状态，使用 `value(x[i])` 获取决策变量的取值。