python - scipy.optimize.minimize，使用整数规划的旅行推销员

Question

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优化工具。这是我的第一个 python 程序和优化程序。由于有两个约束迫使旅行推销员访问(进入和离开)每个节点一次，我想创建具有相同维度的成本矩阵的二元选择“x”矩阵。由于有一个入口，选择矩阵的每一列总和将为 1，并且每个导出也相同。我在使用 scipy.optimize.minimize 方法时遇到问题。我无法将选择矩阵发送到约束函数。如果有人提供帮助，我将不胜感激，提前致谢..(子旅游消除限制尚未实现)

Answer 1

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 示例上找不到更多示例。如果您有任何建议，那就太好了。谢谢