Voyageur utilisant Pyomo

Question

J'essaie d'utiliser pyomo pour résoudre le problème de TSP. J'ai implémenté avec succès avec Python et Gurobi mais ma licence Gurobi a expiré donc je veux maintenant utiliser pyomo et GLPK pour implémenter le problème TSP. C'est ce que je pourrais trouver jusqu'à présent. Il ne fonctionne pas la valeur objective est 0. Pouvez-vous s'il vous plaît aider.

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

La réponse suivante a été testée pour Python 3.5.3 et Pyomo 5.1.1.

1. Les ensembles model.M et model.N n'ont pas été initialisées.

   Cela a pour effet de déclarer des ensembles vides. Donc, si vous exécutez:

   model.con.pprint() 
   

   vous constaterez qu'aucune contrainte n'a été déclarée. De même, model.obj est trivialement égal à 0 et model.c et model.x sont des déclarations vides.

   Vous pouvez résoudre ce problème avec (je suppose que vous voulez indexer de 1 à n):

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

   Depuis model.M et model.N sont des plages en utilisant un RangeSet est probablement plus approprié, par exemple en utilisant les éléments suivants au lieu de ce qui précède:

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

   ci-dessus Pyomo RangeSet est égale à l'ensemble {1, 2, ..., n}.

   En outre, puisque model.M et model.N sont les mêmes, en déclarant que l'un des ensembles est suffisant. Donc, si nous enlevons la déclaration de model.N et remplaçons toute référence à model.N par model.M, nous obtenons le même comportement. L'initialisation de model.c doit être effectuée par (i, j).

   Vous pouvez résoudre ce problème avec (en utilisant la fonction lambda):

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

   index listes Python de 0, model.M et model.N départ de 1 donc nous utilisons l'indice distanceMatrix[i-1][j-1].

2. Les variables model.x ne sont pas binaires.

   Dans un TSP, les variables représentées model.x sont généralement binaires. Résoudre le problème après avoir effectué les étapes 1 et 2 permet aux model.x variables à prendre des valeurs telles que 2.

   Vous pouvez modifier le domaine de model.x en binaire avec:

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

3. La contrainte model.con ne permet pas une tournée TSP.

   model.con équivaut à:

   

   Si nous prenons n = 1, model.con provoquera la solution TSP d'avoir deux villes visitées de la ville à partir du 1 (en supposant que les model.x sont binaires), qui n'est pas autorisé par la définition de TSP.