如何基于ILOG Cplex Java API生成TSP问题的LP约束？

嘿，你已经在TSP的CPLEX Java实现上走了好一段路啦！既然目标函数的随机权重已经搞定，接下来咱们就一步步把TSP需要的线性约束给加上去。

TSP的LP模型主要包含三类核心约束，咱们逐个来实现：

1. 出度约束：每个城市恰好出发一次 #

简单来说，就是对于任意一个城市i，从i出发到其他所有城市的变量x_ij之和必须等于1（只能选一条路离开）。

// 遍历每个城市，添加出度约束
for (int i = 0; i < n; i++) {
    IloLinearExpr outDegreeExpr = cplex.linearExpr();
    for (int j = 0; j < n; j++) {
        if (i != j) { // 排除自己到自己的无效路径
            outDegreeExpr.addTerm(1.0, x[i][j]);
        }
    }
    // 添加等式约束：出度和为1，给约束命名方便后续调试
    cplex.addEq(outDegreeExpr, 1.0, "OutDegree_City_" + (i + 1));
}

2. 入度约束：每个城市恰好到达一次 #

和出度约束对应，任意一个城市j，从其他所有城市到j的变量x_ij之和必须等于1（只能有一条路进来）。

// 遍历每个城市，添加入度约束
for (int j = 0; j < n; j++) {
    IloLinearExpr inDegreeExpr = cplex.linearExpr();
    for (int i = 0; i < n; i++) {
        if (i != j) { // 排除自己到自己的无效路径
            inDegreeExpr.addTerm(1.0, x[i][j]);
        }
    }
    // 添加等式约束：入度和为1
    cplex.addEq(inDegreeExpr, 1.0, "InDegree_City_" + (j + 1));
}

3. 子回路消除约束（关键！） #

只加上面两个约束的话，CPLEX可能会给出多个独立的小回路（比如城市1→2→1，城市3→4→3），这显然不是我们要的TSP解。这里最常用的是Miller-Tucker-Zemlin(MTZ)约束，需要引入额外的辅助变量来避免子回路。

步骤1：定义辅助变量u #

u[i]表示访问城市i的顺序（比如u[0]=1代表第一个访问城市1，u[1]=2代表第二个访问城市2，以此类推）。

// 定义MTZ辅助变量，取值范围是1到n（对应访问顺序）
IloNumVar[] u = cplex.numVarArray(n, 1.0, n);
// 固定第一个城市的顺序（比如城市1的u值为1），避免对称解（减少求解时间）
cplex.addEq(u[0], 1.0, "MTZ_FirstCity_Fix");

步骤2：添加MTZ约束 #

约束公式为：u[i] - u[j] + n*x[i][j] ≤ n-1（其中i≠j，且i、j都不是第一个固定的城市）。这个约束的逻辑是：如果存在从i到j的路径（x[i][j]=1），那么访问i的顺序必须比j早，否则约束会被违反，从而排除子回路。

// 添加MTZ子回路消除约束
for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
        if (i != j) {
            IloLinearExpr mtzExpr = cplex.linearExpr();
            mtzExpr.addTerm(1.0, u[i]);
            mtzExpr.addTerm(-1.0, u[j]);
            mtzExpr.addTerm(n, x[i][j]);
            cplex.addLe(mtzExpr, n - 1, "MTZ_Constraint_" + (i+1) + "_" + (j+1));
        }
    }
}

一些小提示 #

• 给变量和约束命名（比如代码里的OutDegree_City_1），方便后续用CPLEX的工具查看模型、调试问题。
• 如果你的城市数量n很大，MTZ约束会产生O(n²)个约束，可能会影响求解速度，这时可以考虑用其他子回路消除策略（比如割平面法），不过中小规模的TSP用MTZ完全没问题。

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