旅行推销员使用Pyomo

我想用pyomo解决TSP问题。我已经成功实现了使用python和Gurobi，但是我的Gurobi许可证已过期，因此我现在想要使用pyomo和GLPK来实现TSP问题。这是我迄今为止所能想到的。它不工作的目标值是0.你能否请帮助。旅行推销员使用Pyomo

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

来源

2017-04-15 Lisa Mathew

以下答案已经过测试Python 3.5.3和Pyomo 5.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.M替换对model.N的任何参考，我们会得到相同的行为。
model.c的初始化必须根据(i, j)指数进行。从0开始，model.M和model.N从1开始，因此我们使用索引distanceMatrix[i-1][j-1]
```
model.c = Param(model.N, model.M, initialize=lambda model, i, j: distanceMatrix[i-1][j-1]) 
```
Python列表索引：

您可以（使用lambda功能）解决这个问题。
变量model.x不是二元的。

在TSP中，model.x表示的变量通常是二元的。实施后解决问题的步骤1和2允许model.x变量取值如2

您可以更改的model.x域与以二进制：
```
model.x = Var(model.N, model.M, within=Binary) 
```
约束model.con不允许TSP之旅。

model.con等同于：

$model_con$

如果我们取n = 1，model.con将导致TSP解决方案有两个城市从出发城市1访问（假设model.x是二进制），其中TSP的定义是不允许的。

来源

2017-06-21 23:38:53 jmse

旅行推销员使用Pyomo

回答

相关问题