scipy.optimize.minimize，带整数编程的旅行商

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)

I need to implement traveling salesman problem with linear programming. My intention to use python optimization tools. Its my first program in python and optimization programs. Since there are two constraints forces traveling salesman to visit(enter and leave) every node once, I wanted to create binary selection 'x' matrix with the same dimensions of cost matrix. Since there is one entrance every column of the selection matrix will sum to 1 and the same for each exit. I have problems with the usage of scipy.optimize.minimize method. I am not able to send selection matrix to the constraint functions. I will appreciate if anybody helps, thanks in advance.. (sub-tour elimination constraints are not implemented yet)

我需要用线性编程实现旅行商问题。我打算使用python优化工具。它是我在python和优化程序中的第一个程序。由于有两个约束迫使销售人员一次访问(进入和离开)每个节点,我想创建具有相同成本矩阵维度的二元选择'x'矩阵。由于存在一个入口,所以选择矩阵的每列将总和为1并且对于每个出口都相同。我有使用scipy.optimize.minimize方法的问题。我无法将选择矩阵发送到约束函数。如果有人帮忙,我将不胜感激,提前感谢..(亚巡回消除约束尚未实施)

1 个解决方案

#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)

Now i have an edited optimization code using cvxpy packet. But it could not minimize the objective. I could not find more examples on cvxpy MILP examples. If you have any suggestion this will be nice. thanks

现在我有一个使用cvxpy数据包的编辑优化代码。但它无法最小化目标。我找不到关于cvxpy MILP示例的更多示例。如果您有任何建议,这将很好。谢谢