单变量表示道路的PuLP求解TSP问题：建模与代码修正咨询

1. 单变量表示无向边的正确数学建模方式 #

定义二进制无向边变量：对于所有城市对 (i < j)，设 (x_{ij} \in {0,1})，其中 (x_{ij}=1) 当且仅当旅行路径包含城市 (i) 和 (j) 之间的无向边。

对应的约束条件如下：

• 度数约束：每个城市恰好属于2条选中的边（TSP是闭合环，每个点的度数为2）。对任意城市 (i)，有：
  [
  \sum_{\substack{j=1 \ j < i}} x_{ji} + \sum_{\substack{j=1 \ j > i}} x_{ij} = 2
  ]
  简化写法：遍历所有 (j \neq i)，取 (x_{\min(i,j), \max(i,j)}) 求和等于2。
• 子回路消除约束：采用割平面法动态添加，避免生成不包含所有城市的小环。对任意非空真子集 (S \subset V)（(V) 为所有城市的集合），约束子集内部的选中边数不超过 (|S|-1)：
  [
  \sum_{\substack{i < j \ i \in S, j \in S}} x_{ij} \leq |S| - 1
  ]
  注：无需预先添加所有子集约束，而是通过「求解-检测子回路-添加对应约束」的迭代方式处理。

2. 适配无向边变量的findTours函数实现 #

核心逻辑是基于选中的无向边构建图，用BFS/DFS找出所有连通分量（每个分量对应一个子回路）。以下是Python实现示例：

def find_tours(x, num_cities):
    visited = [False] * num_cities
    tours = []
    
    for i in range(num_cities):
        if not visited[i]:
            # BFS遍历连通分量
            queue = [i]
            visited[i] = True
            tour = [i]
            
            while queue:
                current = queue.pop(0)
                # 遍历所有可能的邻接城市，处理无向边
                for j in range(num_cities):
                    if current == j:
                        continue
                    # 取无向边变量的正确索引（i<j）
                    edge_key = (min(current, j), max(current, j))
                    if x[edge_key].varValue > 0.9 and not visited[j]:
                        visited[j] = True
                        tour.append(j)
                        queue.append(j)
            tours.append(tour)
    return tours

说明：

• 遍历每个未访问的城市，用BFS收集所有连通的城市，形成一个子回路候选。
• 访问边时统一取 (min(i,j)) 和 (max(i,j)) 作为变量键，确保正确匹配无向边变量。

3. 当前代码的常见错误修正方案 #

结合无向边TSP的常见坑，修正方向如下：

• 度数约束错误修正：
  原代码可能只累加了 (j > i) 的边，忽略了 (j < i) 的情况。修改为：

  for i in range(num_cities):
    edge_vars = []
    for j in range(num_cities):
        if i != j:
            edge_vars.append(x[(min(i,j), max(i,j))])
    prob += lpSum(edge_vars) == 2, f"DegreeConstraint_{i}"
  

• 子回路消除约束错误修正：
  若原代码沿用了有向TSP的MTZ约束（如 (u_i - u_j + n x_{ij} \leq n-1)），需替换为无向割平面约束。找到子回路 (S) 后，添加约束：

  for tour in tours:
      if len(tour) < num_cities:
          # 生成子集S内的所有无向边
          sub_edge_vars = []
          for idx_i in range(len(tour)):
              for idx_j in range(idx_i+1, len(tour)):
                  i, j = tour[idx_i], tour[idx_j]
                  sub_edge_vars.append(x[(i,j)])
          prob += lpSum(sub_edge_vars) <= len(tour) - 1, f"SubtourElimination_{len(tours)}"
  

• findTours函数错误修正：
  原函数可能只遍历了 (i < j) 的边，导致邻接关系漏检。改为上述实现中统一处理 (min/max) 索引的方式，确保所有选中的无向边都被纳入连通分量检测。

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