CVXPY重复求解规划问题遇无界错误，常量传入则正常

我在用CVXPY求解整数规划问题时，需要多次传入不同参数运行。发现用cp.Parameter传入参数时，问题返回“Problem is unbounded”；但用相同数据作为常量数组直接传入时，能得到正确结果。决策变量x是整数变量，定义为x = cp.Variable(matrix_len, integer=True)。

使用cp.Parameter的实现 #

c= np.array([1,2,3,6])
matrix_len = len(c)
gmma = cp.Parameter(matrix_len,nonneg=True)
gmma.value = [1,2,3,6]
# c = np.array([1.42900, 1.45900, 1.31800, 1.27500, 1.26300, 1.24900, 1.25900])
constraint_matrix = np.zeros((matrix_len,matrix_len),dtype='int')
# 定义约束矩阵 /将矩阵对角线一侧设置为0
for i in range(len(constraint_matrix)):
    for j in range(i + 1):
        constraint_matrix[i][j] = -1
# 生成tmp矩阵
mid_matrix = np.zeros((matrix_len,matrix_len),dtype='int')+1

# 定义约束矩阵 /将矩阵对角线一侧设置为0
for i in range(matrix_len):
    for j in range(i):
        mid_matrix[j][i] = 0

cs_matrix2 = mid_matrix * gmma

# 生成对角矩阵
# d = np.diag(np.zeros(5))
b = np.zeros((matrix_len),dtype='int')+5685    # 定义约束条件的右边向量
c = np.zeros((matrix_len),dtype='int')
x = cp.Variable(matrix_len, integer=True)  # 定义整数决策变量
obj = cp.Minimize(gmma * x)  # 构造目标函数
cons = [constraint_matrix * x <= b,cs_matrix2 * x <= c]  # 构造约束条件
prob = cp.Problem(obj, cons)  # 构建问题模型
prob.solve(solver='CBC', verbose=True )  # 求解问题
print("最优值为:", prob.value+c[0]*5685)

使用常量数组的实现 #

c= np.array([1,2,3,6])
matrix_len = len(c)
# c = np.array([1.42900, 1.45900, 1.31800, 1.27500, 1.26300, 1.24900, 1.25900])
constraint_matrix = np.zeros((matrix_len,matrix_len),dtype='int')
# 定义约束矩阵 /将矩阵对角线一侧设置为0
for i in range(len(constraint_matrix)):
    for j in range(i + 1):
        constraint_matrix[i][j] = -1
# 生成tmp矩阵
mid_matrix = np.zeros((matrix_len,1),dtype='int')+1
cs_matrix2 = mid_matrix*c
# 定义约束矩阵 /将矩阵对角线一侧设置为0
for i in range(len(cs_matrix2)):
    for j in range(i):
        cs_matrix2[j][i] = 0

# 生成对角矩阵
# d = np.diag(np.zeros(5))
b = np.zeros((matrix_len),dtype='int')+5685    # 定义约束条件的右边向量
c = np.zeros((matrix_len),dtype='int')
x = cp.Variable(matrix_len, integer=True)  # 定义整数决策变量
obj = cp.Minimize(c * x)  # 构造目标函数
cons = [constraint_matrix * x <= b,cs_matrix2 * x <= c]  # 构造约束条件
prob = cp.Problem(obj, cons)  # 构建问题模型
prob.solve(solver='CBC', verbose=True )  # 求解问题
print("最优值为:", prob.value+c[0]*5685)

原因分析 #

核心问题出在约束矩阵cs_matrix2的构造逻辑不一致，导致两个版本的约束条件实际生效范围完全不同：

1. 常量数组版本的约束矩阵

   • mid_matrix是(n,1)的列向量，和c（(n,)数组）广播运算后得到(n,n)矩阵，再通过循环将上三角（j<i）置0，最终得到下三角矩阵：每一行i的元素为c[0], c[1], ..., c[i], 0, ..., 0。
   • 约束cs_matrix2 * x <= 0会限制x的前i+1个元素的线性组合不超过0，结合目标函数最小化正系数的线性组合，能有效限制x的取值范围，问题有界。

2. cp.Parameter版本的约束矩阵

   • mid_matrix是(n,n)的全1矩阵，和gmma（(n,)的Parameter）运算后得到每一行都是gmma值的(n,n)矩阵，再通过循环将上三角（j<i）置0，最终得到上三角矩阵：每一行i的元素为0, ..., 0, gmma[i], gmma[i+1], ..., gmma[n-1]。
   • 约束cs_matrix2 * x <= 0对x的前i个元素没有限制，而目标函数是最小化gmma*x（gmma全为正数），此时可以让x的前几个元素取负无穷大，既满足约束（上三角行向量点积为0或负数），又能让目标函数无限小，因此问题被判定为无界。

另外，Parameter版本中重新赋值c = np.zeros((matrix_len),dtype='int')覆盖了初始参数数组，但这不是核心问题，核心是约束矩阵的构造错误。

修复方案 #

将Parameter版本中的mid_matrix改为和常量版本一致的(n,1)列向量，再进行广播运算：

# 修改mid_matrix的定义
mid_matrix = np.zeros((matrix_len,1),dtype='int')+1
cs_matrix2 = mid_matrix * gmma
# 后续置0逻辑保持不变

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