如何为scipy.optimize.linprog定义旅行商问题(TSP)的线性规划约束

问题背景 #

尝试用Python的scipy.optimize.linprog求解TSP的线性规划模型，已完成距离矩阵扁平化，但无法正确构建约束矩阵与向量，现有代码如下：

n = len(d)

TSP_c = [d[i][j] for i in range(n) for j in range(n)]

E = [(i,j) for i in range(len(d)) for j in range(len(d))]
TSP_A = [[1 if k in (i, j) else 0 for (i, j) in E] for k in range(n)]
TSP_b = [2] * n

TSP_res = linprog(TSP_c, TSP_A, TSP_b, bounds = bounds, method = 'simplex')
TSP_res

遇到的问题 #

• 未设置边界时，部分变量值为2，目标函数值为0；
• 设置边界为bounds = [(0, 1)] * n时，抛出ValueError：无法解析该维度的边界；
• 设置正确边界bounds = [(0, 1)] * (n*n)时，变量值为0或1，但目标函数值仍为0，且仅对角线变量为1。

错误原因分析 #

1. 边界维度不匹配：TSP的变量总数为n*n（每个节点对(i,j)对应一个变量），[(0,1)]*n的长度为n，与变量数不匹配，必然报错；
2. 约束逻辑错误：现有约束是统计每个节点在所有边中出现的次数为2，但未区分入度和出度，且未排除i=j的自环路径；
3. 缺失子回路消除约束：仅靠节点度数约束，最优解会选择自环路径（i→i），总距离为0，完全不符合TSP要求——TSP要求形成一个包含所有节点的单一回路，而非多个独立子回路或自环。

修正方案 #

1. 正确构建目标函数 #

将自环路径的距离设为无穷大，避免求解器选择无意义的自环：

TSP_c = []
for i in range(n):
    for j in range(n):
        TSP_c.append(np.inf if i == j else d[i][j])

2. 构建入度/出度约束 #

TSP的基础约束是：每个节点恰好有一条出边和一条入边：

• 出度约束：对每个节点i，所有从i出发的边变量之和为1；
• 入度约束：对每个节点j，所有指向j的边变量之和为1。

3. 添加子回路消除约束（关键） #

对于n个节点，需添加约束：任意非空真子集S的节点，至少有一条边从S指向外部节点。小规模n可手动添加，大规模n需用割平面法逐步迭代添加。

完整修正代码 #

import numpy as np
from scipy.optimize import linprog

# 示例距离矩阵（可替换为自己的矩阵）
d = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])
n = len(d)

# 构建目标函数：自环设为无穷大
TSP_c = []
for i in range(n):
    for j in range(n):
        TSP_c.append(np.inf if i == j else d[i][j])

# 构建等式约束矩阵A_eq和右端向量b_eq
A_eq = []
b_eq = []

# 出度约束：每个节点出度为1
for i in range(n):
    row = [0] * (n * n)
    for j in range(n):
        if j != i:
            row[i * n + j] = 1
    A_eq.append(row)
    b_eq.append(1)

# 入度约束：每个节点入度为1
for j in range(n):
    row = [0] * (n * n)
    for i in range(n):
        if i != j:
            row[i * n + j] = 1
    A_eq.append(row)
    b_eq.append(1)

# 添加子回路消除约束（以n=4为例，手动添加部分约束）
# 约束：子集{0,1}必须有边指向外部
row = [0]*(n*n)
row[0*n+2] = 1  # 0→2
row[0*n+3] = 1  # 0→3
row[1*n+2] = 1  # 1→2
row[1*n+3] = 1  # 1→3
A_eq.append(row)
b_eq.append(1)

# 约束：子集{0,2}必须有边指向外部
row = [0]*(n*n)
row[0*n+1] = 1
row[0*n+3] = 1
row[2*n+1] = 1
row[2*n+3] = 1
A_eq.append(row)
b_eq.append(1)

# 边界：所有变量∈[0,1]（linprog仅支持连续优化，后续需处理整数解）
bounds = [(0, 1)] * (n * n)

# 求解（推荐用highs方法，simplex对大规模问题支持差）
TSP_res = linprog(TSP_c, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
print("最优解状态：", TSP_res.status)
print("目标函数值：", TSP_res.fun)
print("变量值（扁平化）：", TSP_res.x)

注意事项 #

• linprog是连续线性规划求解器，输出的变量值可能为0-1之间的小数，需取整后验证是否为有效TSP回路；
• 子回路消除约束的数量随n指数增长，大规模TSP建议使用专门的TSP求解器（如Concorde）或启发式算法；
• 若需要严格整数解，可使用整数规划库（如PuLP、Gurobi、CPLEX）。

内容的提问来源于stack exchange，提问作者NEWO-o