получение «None» в результате решения проблемы CVXPY - PullRequest
Новая
       8

получение «None» в результате решения проблемы CVXPY

1 голос
/ 21 января 2020

Попытка решить TSP как задачу линейного программирования, используя cvxpy, и с этим возникла проблема. Это мой первый опыт, так что спасибо за помощь. В результате я хочу иметь матрицу с 0 и 1, которая показывает каждый следующий город для продавца.

нужно использовать именно cvxpy

здесь вы можете прочитать теорию

cvxpy website

спасибо за help 

import cvxpy as cp
import numpy as np

np.random.seed(1)
N = 10
distances = np.random.rand(N, N)  

x = cp.Variable((N, N), boolean=True)
u = cp.Variable(N, integer=True)

constraints = []

for j in range(N):                                      
    indices = list(range(0, j)) + list(range(j + 1, N))
    constraints.append(cp.sum(x[indices, j]) == 1)
for i in range(N):
    indices = list(range(0, i)) + list(range(i + 1, N)) 
    constraints.append(cp.sum(x[i, indices]) == 1)
for i in range(1, N):                      
    for j in range(1, N):
        if i != j:
            constraints.append(u[i] - u[j] + N*x[i, j] <= N-1)

for i in range(N):
    for j in range(N):
        if i != j:
            сost += (x[i,j]*distances[i,j]) 

prob = cp.Problem(cp.Minimize(cost), constraints)
prob.solve()
print(prob.value)

получить "None"

похоже на проблему в определении стоимости, но не знаю, как исправить это, может быть, мне стоит использовать cvxpy.multiply или cvxpy.sum?

Ответы [ 2 ]

0 голосов
/ 29 января 2020

не знаю в чем была проблема. возможно что-то с Юпитером. все стало хорошо после освежения спасибо всем за помощь!

0 голосов
/ 24 января 2020

Стандартный MIP-решатель, поставляемый с cvxpy, является просто доказательством концепции и очень нестабилен в не крошечных случаях. Подобные вещи случаются тогда, и вы мало что можете сделать.

Как и просил Эрвин в комментариях выше: активируйте verbose=True, и вы можете распознать используемый решатель. Я догадываюсь: ECOS_BB. Это единственный вариант, доступный при установке по умолчанию.

Ситуация с развертыванием решателя MIP, который:

  • легко устанавливается на windows
  • , высокого качества
  • с открытым исходным кодом

не велик.

Самый простой подход для получения пригодного для использования на windows - это использование предварительно созданного glpk через cvxopt.

...