scipy.optimize.minimize, коммивояжер с целочисленным программированием - PullRequest
Новая
       12

scipy.optimize.minimize, коммивояжер с целочисленным программированием

0 голосов
/ 21 мая 2018 
import numpy as np;
import math;
import random;
from scipy.optimize import minimize;


def matrixmult (A, B):
    rows_A = len(A)
    cols_A = len(A[0])
    rows_B = len(B)
    cols_B = len(B[0])

    Z = [[0 for row in range(rows_B)] for col in range(cols_A)]

    for i in range(cols_A):
        for j in range(rows_A):
            #for k in range(cols_A):
                Z[i][j] += A[i][j] * B[i][j]


    return Z

def constraint1(x):
    A=x
    rows_X = cols_X = len(x)
    ad = np.ones((len(x),1))  #makes a 7x1 array of ones 
    ad1 = x.sum(axis=1) # makes 7x1 array, each element is sum of each rows
    ad2 = np.matrix(ad1) 

    for i in range(len(x)):
        ad[i] = ad[i] - ad2[i] # sum of each row in a binary matrix must be 1 to indicate there is only one entrance or exit for each node
    #for j in range(cols_X):
     #ad = ad - ad1[i]


    return ad

def constraint2(x):
    rows_X = cols_X = len(x)
    ad3 = np.ones((1,len(x)))
    ad4 = x.sum(axis=0)
    ad5 = np.matrix(ad4)

    for i in range(len(x)):
        ad3[i] = ad3[i] - ad5[i]
    #for j in range(cols_X):
     #ad = ad - ad1[i]

    return ad3

def total(C):

    C = np.array([[np.nan,3,5,np.nan,np.nan,np.nan,3],[3,np.nan,3,7,np.nan,np.nan,11],[5,3,np.nan,3,np.nan,np.nan,np.nan],[np.nan,7,3,np.nan,3,9,11],[np.nan,np.nan,np.nan,3,np.nan,3,np.nan],[np.nan,np.nan,np.nan,9,3,np.nan,3],[3,11,np.nan,11,np.nan,3,np.nan]])

    X = [[0 for row in range(len(C))] for col in range(len(C[0]))]

    for i in range(len(C[0])):
        for j in range(len(C)):
            if math.isnan(C[i][j]) == False :
                X[i][j] +=  random.randint(0,1)
            else :
                X[i][j]==np.nan



    CX = matrixmult (C, X)
    cx = np.array(CX)
    x = np.matrix(X)
    print(x.sum(axis=1))
    print(x.sum(axis=0))
    print(x)
    print(cx)
    tot = 0
    for i in range(len(cx[0])):
        for j in range(len(cx)):
            if math.isnan(cx[i][j]) == False :
                #print (i,j)
                tot += cx[i][j]


     #for i in range(len(cx[0])):
            #for j in range(len(cx)):
                #if math.isnan(cx[i][j]) == False :
                    #print (i,j)
    return tot


C = np.array([[np.nan,3,5,np.nan,np.nan,np.nan,3],[3,np.nan,3,7,np.nan,np.nan,11],[5,3,np.nan,3,np.nan,np.nan,np.nan],[np.nan,7,3,np.nan,3,9,11],[np.nan,np.nan,np.nan,3,np.nan,3,np.nan],[np.nan,np.nan,np.nan,9,3,np.nan,3],[3,11,np.nan,11,np.nan,3,np.nan]])


con1 = {'type' : 'eq', 'fun' : constraint1}
con2 = {'type' : 'eq', 'fun' : constraint2}

cons = [con1,con2]

path = minimize(total, 12,method='SLSQP', jac=None, bounds=None, tol=None, callback=None, constraints = cons)

print(path)

Мне нужно реализовать задачу коммивояжера с помощью линейного программирования.Мое намерение использовать инструменты оптимизации Python.Это моя первая программа на питоне и в программах оптимизации.Поскольку существуют два ограничения, заставляющие коммивояжера посещать (входить и выходить) каждый узел один раз, я хотел создать матрицу двоичного выбора «x» с одинаковыми размерами матрицы затрат.Поскольку существует один вход, каждый столбец матрицы выбора будет суммироваться в 1 и одинаков для каждого выхода.У меня проблемы с использованием метода scipy.optimize.minimize.Я не могу отправить матрицу выбора в функции ограничения.Буду признателен, если кто-нибудь поможет, заранее спасибо .. (ограничения на исключение из суб-тура еще не реализованы)

1 Ответ

0 голосов
/ 23 мая 2018 
from cvxpy import *
import numpy as np
import math;
import random;

n = 7
#X = Bool(n , n)
#Y = Bool(n , 1)
#C = np.random.randint(1,5,(n,n))
C = np.array([[np.nan,3,5,np.nan,np.nan,np.nan,3],[3,np.nan,3,7,np.nan,np.nan,11],[5,3,np.nan,3,np.nan,np.nan,np.nan],[np.nan,7,3,np.nan,3,9,11],[np.nan,np.nan,np.nan,3,np.nan,3,np.nan],[np.nan,np.nan,np.nan,9,3,np.nan,3],[3,11,np.nan,11,np.nan,3,np.nan]])


#X = [[0 for row in range(len(C))] for col in range(len(C[0]))]
X = np.zeros((n,n))


for i in range(n):
    for j in range(n):
        if math.isnan(C[i][j]) == False :
            X[i][j] +=  random.randint(0,1)
        else :
            X[i][j]== np.nan

#x = np.array(X, dtype = np.float64)
P = C*X
nodes = []

tot = 0
for i in range(n):
    for j in range(n):
        if math.isnan(P[i][j]) == False :   
            tot += P[i][j]
            if(P[i][j] >0):
                print (i,j)
                nodes.append((i,j))
print(nodes)
print(len(nodes))


objective = Minimize(tot)
constraints = []
constraints.append( sum_entries( X, axis=0 ) == 1 )
constraints.append( sum_entries( X, axis=1 ) == 1 )
#constraints.append( sum_entries(Y) == C )

prob = Problem(objective, constraints)
prob.solve(solver=GLPK_MI)
print (prob.value)
print(tot)
print(C)
print(X)
print(P)
#print(objective)

Теперь у меня есть отредактированный код оптимизации с использованием пакета cvxpy.Но это не могло минимизировать цель.Я не смог найти больше примеров на примерах cvxpy MILP.Если у вас есть предложения, это будет хорошо.спасибо

...