CODEWITHSUNDEEP
pythonpyomo
Lisa Mathew
Lisa Mathew

Reputation: 325

Traveling Salesman using Pyomo

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

Upvotes: 2

Views: 1812

Answers (1)

jmse
jmse

Reputation: 81

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

  1. The sets model.M and model.N have not been initialised.

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

    model.con.pprint()

    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.

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

    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)

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

    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.

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

    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 lists index from 0, model.M and model.N start from 1 therefore we use the index distanceMatrix[i-1][j-1].

  3. The variables model.x are not binary.

    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.

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

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

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

    model.con is equivalent to:

    model_con

    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.

Upvotes: 5

Related Questions