使用Pulp求解TSP时，734城市实例LpProblem变为NoneType的问题求助

问题背景 #

使用Python Pulp库结合GUROBI_CMD求解旅行商问题（TSP）时，在29、38、194个城市的小规模数据集上能正常运行并得到最优解，但处理734个城市的uy734数据集时，创建的LpProblem对象变为NoneType，导致后续调用prob.variables()、prob.solve()等操作失败。

可能原因分析 #

1. 内存资源耗尽：734城市的MTZ模型会生成海量变量与约束：

   • 二进制路径变量：734×734=538756个
   • MTZ子回路消除约束：原代码未过滤i=j的无效情况，生成了733×733=537289个约束（其中733个是无效约束）
     如此规模的模型在构建过程中可能耗尽Python进程的可用内存，导致Pulp无法正常初始化LpProblem对象，最终返回None。

2. GUROBI_CMD的调用缺陷：GUROBI_CMD通过命令行工具传递模型数据，当模型过大时，数据传输过程中可能出现异常，导致Pulp无法正确处理求解器返回的结果，使prob对象变为None。

3. Pulp的大规模模型处理限制：Pulp的内部数据结构在处理超大规模约束/变量时，可能因未做内存优化出现故障，尤其是在循环添加约束的阶段。

解决方案 #

1. 修复MTZ约束的冗余问题 #

恢复mtz函数中i != j的判断，移除无效约束，减少内存占用：

def mtz(n, prob, cidades, var):
    u = LpVariable.dicts('u', (i for i in cidades), 1, n-1, LpInteger)
    for i in cidades[1:]:
        for j in cidades[1:]:
            if i != j:  # 过滤i=j的无效约束
                prob += u[i] - u[j] + (n - 1) * var[i][j] <= n - 2
    return prob

2. 切换为GUROBI求解器（而非GUROBI_CMD） #

直接使用Gurobi的Python API（需安装Gurobi并激活许可证），避免命令行数据传输的开销与异常：

# 替换solvingMTZ中的solve调用语句
prob.solve(GUROBI(timeLimit=timelimit, msg=1, gapRel=0))

3. 增加内存监控与日志定位 #

添加内存使用日志，确认模型构建的哪个阶段出现问题：

import psutil

def solvingMTZ(cidades, destinos, n, costs, file):
    prob = LpProblem("Teste", LpMinimize)
    print(f"初始内存占用: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    road = [(cid_i, cid_j) for cid_i in cidades for cid_j in destinos]
    var = LpVariable.dicts("Road", (cidades, destinos), 0, 1, LpInteger)
    print(f"创建路径变量后内存占用: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    prob += lpSum([var[cid_i][cid_j] * costs[cid_i][cid_j] for (cid_i, cid_j) in road])
    print(f"添加目标函数后内存占用: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    # 分批添加入度约束并打印日志
    for idx, i in enumerate(cidades):
        prob += lpSum([var[i][cid_j] for cid_j in destinos if i != cid_j]) == 1
        if idx % 100 == 0:
            print(f"已添加{idx+1}个入度约束，当前内存: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    # 分批添加出度约束并打印日志
    for idx, j in enumerate(destinos):
        prob += lpSum([var[cid_i][j] for cid_i in cidades if j != cid_i]) == 1
        if idx % 100 == 0:
            print(f"已添加{idx+1}个出度约束，当前内存: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    prob = mtz(n, prob, cidades, var)
    print(f"添加MTZ约束后内存占用: {psutil.Process().memory_info().rss / 1024 ** 2:.2f} MB")
    
    timelimit = max_time
    start = time.time()
    prob.solve(GUROBI(timeLimit=timelimit, msg=1, gapRel=0))
    end = time.time()
    timelimit = timelimit - end + start
    print(timelimit)
    
    print_prob(prob, timelimit)
    make_node_fileMTZ(prob, file, timelimit)
    return

4. 调整系统内存限制 #

• Linux/macOS：使用ulimit -v <内存大小>命令增加进程可用虚拟内存（例如ulimit -v 16777216设置为16GB）。
• Windows：调整系统虚拟内存（页面文件）大小，分配更大的空间。

5. 考虑更高效的TSP模型 #

MTZ模型的约束数量为O(n²)，对于大规模TSP可以考虑使用**懒约束（Lazy Constraints）**来动态添加子回路消除约束，减少初始模型的规模。Gurobi支持懒约束，可通过Pulp的LpSolverDefault或直接调用Gurobi API实现。

内容的提问来源于stack exchange，提问作者Gabriel Sanches da Silva