使用CVXPY优化最短路径时的约束条件问题求助

问题背景 #

你正在用CVXPY完成运筹学最短路径练习，asig是一个布尔型变量矩阵，希望添加约束：对所有i、j，asig[i,j] != asig[j,i]，但不清楚如何在CVXPY中实现该约束。

约束转化思路 #

CVXPY不支持直接使用!=作为约束条件，它要求约束必须是线性或凸形式。对于布尔变量（仅取0或1），asig[i,j] != asig[j,i]可以等价转化为线性约束：
当i≠j时，asig[i,j] + asig[j,i] = 1
这个等式的逻辑是：两个布尔变量不能同时为0或同时为1，只能一个为0、一个为1，恰好满足“不等”的要求。

结合你现有代码中的cond_3 = cp.diag(asig) == 0（对角线元素为0），无需处理i=j的情况，只需对i≠j的组合添加约束即可。

修改后的完整代码 #

import cvxpy as cp
import pandas as pd
import numpy as np

# 替换为你实际的nc值
nc = 4  

asig = cp.Variable((nc+1, nc+1), boolean=True) 

excel_1 = 'https://docs.google.com/spreadsheets/d/e/2PACX-1vTAnqb05pTL8xrEzLgHPvi_xb3ciSiPf9xEzi5mx3id1a7ySvXbSEzDewsYwZ5_4A/pub?output=xlsx'
tabla_dist = pd.read_excel(excel_1, header=None)
coef_dist = np.zeros((nc+1, nc+1))

for i in range(0, nc+1):
    for j in range(0, nc+1):
        coef_dist[i][j] = tabla_dist.iloc[i,j]

# 直接使用常数矩阵作为系数，无需cp.Parameter
coef_costos = coef_dist

z_min = cp.Minimize(cp.sum(cp.multiply(coef_costos, asig)))

cond_1 = cp.sum(asig, axis=1) == 1
cond_2 = cp.sum(asig, axis=0) == 1
cond_3 = cp.diag(asig) == 0

restricciones = [cond_1, cond_2, cond_3]

# 添加asig[i,j] != asig[j,i]的约束（仅处理i<j避免重复）
for i in range(nc+1):
    for j in range(i+1, nc+1):
        restricciones.append(asig[i,j] + asig[j,i] == 1)

problema = cp.Problem(z_min, restricciones)
problema.solve()
print("Estado de la solución:", problema.status)
print(problema.value)
print(asig.value)

matriz = np.array(asig.value)

for i in range(nc+1):
    for j in range(nc+1):
        if matriz[i][j] == 1:
            print(i,j)

额外说明 #

1. 遍历j时从i+1开始，避免重复添加相同约束（比如i=0,j=1和i=1,j=0是同一个约束），减少计算量；
2. 原代码中coef_costos = cp.Parameter(...)的用法冗余，直接使用常数矩阵coef_dist作为系数即可；
3. 结合现有约束，最终得到的asig是一个无向图的完美匹配置换矩阵，符合最短路径类问题的需求。

内容的提问来源于stack exchange，提问作者Natalia Giraldo