基于scipy.optimize.minimize的整数规划旅行商问题实现求助

嘿，我看你第一次用Python和Scipy做旅行商问题的线性规划，卡在了约束函数接收变量的环节——这确实是刚开始用scipy.optimize.minimize时容易踩的坑，核心问题是minimize会把决策变量扁平化传递给目标函数和约束函数，而不是直接传二维矩阵，另外你的目标函数和约束函数的参数、返回值格式也需要调整。

下面我会一步步帮你修正代码，解释关键问题点：

核心问题分析 #

• 决策变量的扁平化：minimize要求决策变量是一维数组，你定义的二维选择矩阵x需要先转成一维，在函数内部再reshape回二维矩阵。
• 目标函数参数错误：你的total函数现在接收的是成本矩阵C，但实际上minimize会把决策变量（扁平化的x）作为第一个参数传入，C应该作为全局变量或者用闭包传递。
• 约束函数的返回值格式：约束函数需要返回一维数组，每个元素对应一个等式约束（等于0），而不是矩阵。
• 错误的矩阵乘法：你自己写的matrixmult逻辑有误，TSP的目标函数应该是成本矩阵和选择矩阵的元素对应相乘后求和，直接用numpy的np.sum或者点积更高效准确。

修正后的完整代码 #

import numpy as np
from scipy.optimize import minimize

# 定义成本矩阵（NaN表示不可通行的路径）
C = np.array([
    [np.nan, 3, 5, np.nan, np.nan, np.nan, 3],
    [3, np.nan, 3, 7, np.nan, np.nan, 11],
    [5, 3, np.nan, 3, np.nan, np.nan, np.nan],
    [np.nan, 7, 3, np.nan, 3, 9, 11],
    [np.nan, np.nan, np.nan, 3, np.nan, 3, np.nan],
    [np.nan, np.nan, np.nan, 9, 3, np.nan, 3],
    [3, 11, np.nan, 11, np.nan, 3, np.nan]
])
n = C.shape[0]  # 节点数量

# 目标函数：计算总旅行成本
def total(x_flat):
    # 将扁平化的变量转为二维矩阵
    x = x_flat.reshape((n, n))
    # 处理NaN：不可通行的路径对应的x必须为0，所以成本设为0
    cost_matrix = np.where(np.isnan(C), 0, C)
    # 计算总成本：元素对应相乘后求和
    total_cost = np.sum(cost_matrix * x)
    return total_cost

# 约束1：每行的和为1（每个节点恰好出发一次）
def constraint_row_sum(x_flat):
    x = x_flat.reshape((n, n))
    # 返回每行和减1的数组，要求每个元素等于0
    return x.sum(axis=1) - 1

# 约束2：每列的和为1（每个节点恰好到达一次）
def constraint_col_sum(x_flat):
    x = x_flat.reshape((n, n))
    # 返回每列和减1的数组，要求每个元素等于0
    return x.sum(axis=0) - 1

# 约束3：不可通行的路径对应的x必须为0（避免选择不存在的路径）
def constraint_invalid_paths(x_flat):
    x = x_flat.reshape((n, n))
    # 找到所有C为NaN的位置，返回这些位置的x值，要求等于0
    invalid_indices = np.where(np.isnan(C))
    return x[invalid_indices]

# 构造约束列表
cons = [
    {'type': 'eq', 'fun': constraint_row_sum},
    {'type': 'eq', 'fun': constraint_col_sum},
    {'type': 'eq', 'fun': constraint_invalid_paths}
]

# 初始猜测：生成一个扁平化的初始值，尽量接近可行解
x0 = np.random.rand(n*n)
# 归一化每行，让初始值的行和接近1（帮助优化收敛）
x0 = x0.reshape((n, n))
x0 = x0 / x0.sum(axis=1, keepdims=True)
x0 = x0.flatten()

# 变量边界：x是二进制变量，所以每个元素在[0,1]之间
bounds = [(0, 1) for _ in range(n*n)]

# 执行优化
path = minimize(
    total,
    x0=x0,
    method='SLSQP',
    bounds=bounds,
    constraints=cons,
    tol=1e-6
)

# 输出结果
print("优化结果详情：")
print(path)

# 将结果转为二维矩阵并打印（浮点型，可后续取整）
x_opt = path.x.reshape((n, n))
print("\n最优选择矩阵（保留3位小数）：")
print(np.round(x_opt, 3))

# 计算最优总成本
print("\n最优总成本：", path.fun)

关键修改点解释 #

1. 扁平化变量处理：所有函数（目标函数、约束函数）都接收一维的x_flat，然后用reshape((n, n))转成二维矩阵，这是minimize要求的标准格式。
2. 目标函数重构：直接用numpy的元素相乘和求和计算总成本，同时处理了NaN的情况，避免不可通行路径影响结果。
3. 约束函数修正：
   • 行和、列和约束返回一维数组，确保每个节点进出各一次。
   • 新增不可通行路径约束，强制这些位置的x为0，避免优化器选择无效路径。
4. 初始值与边界：用归一化的随机数组作为初始值，帮助优化器更快收敛；设置变量边界为[0,1]，符合二进制变量的范围。

后续注意事项 #

• 子回路消除：你提到还没实现子回路消除，这是TSP线性规划的关键约束，否则优化结果可能出现多个独立小回路。可以通过添加Miller-Tucker-Zemlin约束来解决。
• 整数规划：Scipy的minimize是连续优化器，得到的是浮点解，需要后续取整；如果需要更精准的整数解，建议使用专门的整数规划库（如PuLP、Gurobi）。

内容的提问来源于stack exchange，提问作者user9824636