Коммивояжер с Pyomo

Я пытаюсь использовать 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')

python pyomo
person Lisa Mathew    schedule 15.04.2017    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Следующий ответ был протестирован для 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 эквивалентно:

    model_con

    Если мы возьмем n = 1, model.con приведет к тому, что решение TSP посетит два города из начального города 1 (при условии, что model.x являются двоичными), что не разрешено определением TSP.

person jmse    schedule 21.06.2017