Julia JuMP 在解决 TSP 时速度减慢/挂起

Question

尝试优化 JuMP 上的线性规划问题（旅行商问题）

基本模型运行良好，但是当我尝试运行第二个模型（消除了 subtour ）时，Julia 没有响应，我让它运行了 15 分钟，但仍然没有任何反应

基本模型（工作正常）：

D = zeros(58,58) #the actual dataset is irrelevant to the freezing problem

#basic method (no subtour elimination)

using JuMP
using GLPK
using Formatting

n = 58;
N = collect(1:n);

m = Model(GLPK.Optimizer)

@variable(m, x[i in N, j in N], Bin);

@objective(m, Min, sum(x[i,j] * D[i,j] for i in N for j in N));

@constraint(m, [i in N], sum(x[i,j] for j in N) == 1);
@constraint(m, [j in N], sum(x[i,j] for i in N) == 1);

@constraint(m, [i in N], x[i,i] == 0);

optimize!(m)

printfmt("Minimal cost (basic TSP) == {:d}\n",objective_value(m))

第二个模型（挂在 !optimize(m) 上）：

#subtour elimination using potential method

@variable(m, p[i in N], Int);

@constraint(m, [i in N], 1 <= p[i] <= n);

@constraint(m, p[1] == 1);

for i in N
    for j in 2:n
        if i != j
            @constraint(m, p[i] - p[j] + n*x[i,j] <= n - 1); #having this constraint on makes the solver freeze
        end
    end
end

optimize!(m) #solver freezes here

printfmt("Minimal cost (potential method) == {:d}\n",objective_value(m))

尝试为第二个模型创建不同的模型，而不是仅仅添加到第一个模型，尝试将每个模型分离为一个函数，尝试使用相同方法的替代公式，但没有任何效果

我的代码做错了什么？我不知道朱莉娅是完全冻结了还是只是太慢了

Answer 1

您可以使用迭代方法或编写回调，而不是添加所有更微妙的消除约束。

有关更多详细信息，请参阅 JuMP 文档：https://jump.dev/JuMP.jl/stable/tutorials/algorithms/tsp_lazy_constraints/

您还可以尝试不同的求解器，例如 HiGHS 或 Gurobi。 GLPK 解决 MILP 的速度相当慢。

Answer 2

使用 Cplex 作为求解器，使用 58 个城市（随机放置、欧几里德距离、默认求解器设置），我看到：

----    141 PARAMETER stats  collected statistics

                          obj  iterations       nodes     seconds

MTZ(int u)            569.089 1061905.000   83982.000      28.750
MTZ(relaxed u)        569.089 1153378.000   77797.000      23.828
lifted(int u)         569.089 1623901.000  105898.000      20.813
lifted(relaxed u)     569.089 1287205.000   73390.000      19.235

我在模型中将你的

p

变量称为

u

。我们可以选择使它们为整数或连续。这里没有太大区别。

你的版本叫MTZ，很久以前发布的：

 Miller, C., A. Tucker, R. Zemlin. 1960, Integer programming 
 formulation of traveling salesman problems. J. ACM 7 326-329

提升版本取自：

Desrochers, M., Laporte, G., Improvements and extensions to the 
Miller-Tucker-Zemlin subtour elimination constraints, Operations 
Research Letters, 10 (1991) 27-36.

结论：众所周知，MTZ 速度很慢，但 58 个城市完全在优秀求解器的能力范围内。