python - 使用 Pyomo 的旅行推销员

Question

我正在尝试使用 pyomo 来解决 TSP 问题。我已经使用 python 和 Gurobi 成功实现了，但是我的 Gurobi 许可证已过期，所以我现在想使用 pyomo 和 GLPK 来实现 TSP 问题。到目前为止，这是我能想到的。它不工作，目标值为 0。你能帮忙吗？

from pyomo.environ import * 
from pyomo.opt import SolverFactory
import pyomo.environ

n=13
distanceMatrix=[[0,8,4,10,12,9,15,8,11,5,9,4,10],
    [8,0,7,6,8,6,7,10,12,9,8,7,5],
    [4,7,0,7,9,5,8,5,4,8,6  ,10,8],
    [10,6   ,7,0,6,11,5 ,9,8,12,11,6,9],
    [12,8   ,9,6,   0,7,9,6,9,8,4,11,10],
    [9,6,5,11,7,0,10,4,3,10,6,5,7],
    [15,7   ,8,5,9,10,0,10,9,8,5,9,10],
    [8,10   ,5,9,6,4,10,0,11,5,9,6,7],
    [11,12,4,8, 9,3,9,11,0, 9,11,11,6],
    [5,9,8,12,8,10,8,5,9,0,6,7,5],
       [9,8,6,11,4,6,5,9,11,6,0,10,7],
       [4,7,10,6,11,5,9,6,11,7,10,0,9],
       [10,5,8,9,10,7,10,7,6,5,7,9,0]] 
startCity = 0

model = ConcreteModel()
model.N=Set()
model.M=Set()
model.c=Param(model.N,model.M, initialize=distanceMatrix)
model.x=Var(model.N,model.M, within=NonNegativeReals)
def obj_rule(model):            
    return sum(model.c[n,j]*model.x[n,j] for n in model.N for j in    model.M)
model.obj = Objective(rule=obj_rule,sense=minimize)
def con_rule(model, n):
    return sum(model.x[j,n] for j in model.M if j < n) + sum(model.x[n,j] for j in Model.M if j > i) == 2

model.con = Constraint(model.N, rule=con_rule,doc='constraint1')
opt = SolverFactory("glpk")
results = opt.solve(model)
results.write()
print('Printing Values')

Answer 1

以下答案已针对 Python 3.5.3 和 Pyomo 5.1.1 进行了测试。

1. 集合model.M 和model.N 尚未初始化。

   这具有声明空集的效果。所以如果你运行:

   model.con.pprint()
   

   你会发现没有声明约束。同样，model.obj 通常等于 0，model.c 和 model.x 是空声明。

   你可以解决这个问题(我假设你想从 1 到 n 建立索引):

   model.M = Set(initialize=range(1, n+1))
   model.N = Set(initialize=range(1, n+1))
   

   由于 model.M 和 model.N 是使用 RangeSet 的范围可能更合适，即使用以下而不是以上:

   model.M = RangeSet(n)
   model.N = RangeSet(n)
   

   上面的 Pyomo RangeSet 等于集合 {1, 2, ..., n}。

   此外，由于 model.M 和 model.N 相同，声明其中一个集合就足够了。因此，如果我们删除 model.N 的声明并将对 model.N 的任何引用替换为 model.M，我们会得到相同的行为。

2. model.c 的初始化必须根据 (i, j) 索引执行。

   您可以通过(使用 lambda 函数)修复此问题:

   model.c = Param(model.N, model.M, initialize=lambda model, i, j: distanceMatrix[i-1][j-1])
   

   Python 列出索引从 0 开始，model.M 和 model.N 从 1 开始，因此我们使用索引 distanceMatrix[i-1][j- 1].

3. 变量 model.x 不是二进制的。

   在 TSP 中，model.x 表示的变量通常是二进制的。在执行步骤 1 和 2 后解决问题允许 model.x 变量采用诸如 2 之类的值。

   您可以将 model.x 的域更改为二进制:

   model.x = Var(model.N, model.M, within=Binary)
   

4. 约束 model.con 不允许 TSP 游览。

   model.con 等同于:

   

   如果我们取 n = 1，model.con 将导致 TSP 解决方案从城市 1 开始访问两个城市(假设 model.x 是二进制的)，这是 TSP 定义所不允许的。