使用 Pyomo 的旅行推销员 [英] Traveling Salesman using Pyomo

问题描述

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

I am trying to use pyomo to solve TSP problem. I have successfully implemented using python and Gurobi but my Gurobi license expired so I want to now use pyomo and GLPK to implement the TSP problem. This is what I could come up with so far. It is not working the objective value is 0. Can you please help.

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')

推荐答案

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

The following answer has been tested for Python 3.5.3 and Pyomo 5.1.1.

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

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

This has the effect of declaring empty sets. So if you run:

model.con.pprint()

您会发现没有声明任何约束.类似地，model.obj 等于 0，model.c 和 model.x 是空声明.

you will find that no constraints have been declared. Similarly, model.obj is trivially equal to 0 and model.c and model.x are empty declarations.

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

You can fix this with (I'm assuming that you want to index from 1 to n):

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

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

Since model.M and model.N are ranges using a RangeSet is probably more suitable, i.e. using the following instead of the above:

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

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

The above Pyomo RangeSet is equal to the set {1, 2, ..., n}.

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

Furthermore, since model.M and model.N are the same, declaring one of the sets is sufficient. So if we remove the declaration of model.N and replace any reference to model.N with model.M, we get the same behaviour.

model.c 的初始化必须按照 (i, j) 索引进行.

The initialisation of model.c has to be carried out per (i, j) index.

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

You can fix this with (using lambda function):

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].

Python lists index from 0, model.M and model.N start from 1 therefore we use the index distanceMatrix[i-1][j-1].

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

The variables model.x are not binary.

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

In a TSP, the variables that model.x represent are usually binary. Solving the problem after carrying out steps 1 and 2 allows the model.x variables to take values such as 2.

您可以使用以下命令将 model.x 的域更改为二进制:

You can change the domain of model.x to binary with:

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

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

The constraint model.con does not allow a TSP tour.

model.con 等价于:

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

If we take n = 1, model.con will cause the TSP solution to have two cities visited from starting city 1 (assuming that the model.x are binary), which is not allowed by the definition of TSP.

这篇关于使用 Pyomo 的旅行推销员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！