Gurobi求解旅行商问题的官方例程

求解时间

• 在该问题上，gurobi 11 快于 gurobi 12。

代码

#!/usr/bin/env python3.11

# 版权所有 2025, Gurobi Optimization, LLC

# 使用惰性约束（消除子循环）解决随机生成的点集上的旅行商问题（TSP）。

import logging
import math
import random
from collections import defaultdict
from itertools import combinations
import gurobipy as gp
from gurobipy import GRB

def shortest_subtour(edges):
    """给定一个边列表，返回通过这些边找到的最短子回路（作为节点列表）。
    假设边列表中的每个节点恰好有一条“入”边和一条“出”边。"""

    # 创建一个从每个节点到其邻居的映射
    node_neighbors = defaultdict(list)
    for i, j in edges:
        node_neighbors[i].append(j)
    assert all(len(neighbors) == 2 for neighbors in node_neighbors.values())

    # 通过边来寻找回路。每次找到一个新的回路时，记录当前找到的最短回路，
    # 并从尚未访问的节点重新开始。
    unvisited = set(node_neighbors)
    shortest = None
    while unvisited:
        cycle = []
        neighbors = list(unvisited)
        while neighbors:
            current = neighbors.pop()
            cycle.append(current)
            unvisited.remove(current)
            neighbors = [j for j in node_neighbors[current] if j in unvisited]
        if shortest is None or len(cycle) < len(shortest):
            shortest = cycle

    assert shortest is not None
    return shortest


class TSPCallback:
    """实现TSP惰性约束的回调类。在MIPSOL回调中，检查解是否包含子回路，
    并在需要时添加子回路消除约束。"""

    def __init__(self, nodes, x):
        self.nodes = nodes
        self.x = x

    def __call__(self, model, where):
        """回调入口点：当找到新的解时调用惰性约束例程。
        如果用户代码中发生异常，则停止优化。"""
        if where == GRB.Callback.MIPSOL:
            try:
                self.eliminate_subtours(model)
            except Exception:
                logging.exception("在MIPSOL回调中发生异常")
                model.terminate()

    def eliminate_subtours(self, model):
        """提取当前解，检查是否存在子回路，并在找到子回路时添加惰性约束以切断当前解。
        假设当前处于MIPSOL状态。"""
        values = model.cbGetSolution(self.x)
        edges = [(i, j) for (i, j), v in values.items() if v > 0.5]
        tour = shortest_subtour(edges)
        if len(tour) < len(self.nodes):
            # 为回路中的每对城市添加子回路消除约束
            model.cbLazy(
                gp.quicksum(self.x[i, j] for i, j in combinations(tour, 2))
                <= len(tour) - 1
            )


def solve_tsp(nodes, distances):
    """
    使用以下基本公式解决密集对称TSP问题：

    min  sum_ij d_ij x_ij
    s.t. sum_j x_ij == 2   forall i in V
         x_ij binary       forall (i,j) in E

    并使用惰性约束消除子回路。
    """

    with gp.Env() as env, gp.Model(env=env) as m:
        # 创建变量，并将对称键添加到结果字典'x'中，
        # 使得(i, j)和(j, i)引用同一个变量。
        x = m.addVars(distances.keys(), obj=distances, vtype=GRB.BINARY, name="e")
        x.update({(j, i): v for (i, j), v in x.items()})

        # 创建度-2约束
        for i in nodes:
            m.addConstr(gp.quicksum(x[i, j] for j in nodes if i != j) == 2)

        # 使用惰性约束优化模型以消除子回路
        m.Params.LazyConstraints = 1
        cb = TSPCallback(nodes, x)
        m.optimize(cb)

        # 将解提取为一个回路
        edges = [(i, j) for (i, j), v in x.items() if v.X > 0.5]
        tour = shortest_subtour(edges)
        assert set(tour) == set(nodes)

        return tour, m.ObjVal


if __name__ == "__main__":

    # 在二维空间中生成n个随机点
    random.seed(3)
    nodes = list(range(100))
    points = [(random.randint(0, 100), random.randint(0, 100)) for i in nodes]

    # 计算每对点之间的欧几里得距离并存储在字典中
    distances = {
        (i, j): math.sqrt(sum((points[i][k] - points[j][k]) ** 2 for k in range(2)))
        for i, j in combinations(nodes, 2)
    }

    tour, cost = solve_tsp(nodes, distances)

    print("")
    print(f"最优回路: {tour}")
    print(f"最优成本: {cost:g}")
    print("")