CVXPY整数规划中如何实现每行非零元素数<2的约束？

错误原因分析 #

• 第一个代码错误：cp.sum(x >= 0, 1) 中，x >= 0 返回的是CVXPY的Inequality对象，并非数值表达式，无法直接参与求和运算，因此触发TypeError。
• 第二个代码错误：使用log构造的约束违反了CVXPY的DCP（Disciplined Convex Programming）规则，log是凹函数，这类约束无法被CVXPY的求解器处理，因此触发DCPError。

正确实现方法 #

根据矩阵x的变量类型，分两种场景处理：

场景1：x是0-1整数矩阵（元素仅取0或1）

此时每行非零元素的数量等于该行元素的和，直接添加线性约束即可：

import cvxpy as cp

# 假设x是形状为(n_rows, n_cols)的0-1整数变量矩阵
x = cp.Variable((n_rows, n_cols), integer=True, boolean=True)
# 约束：每行非零元素数≤1（即小于2）
constraint2 = [cp.sum(x[i, :]) <= 1 for i in range(n_rows)]

场景2：x是一般整数矩阵（元素可取任意非零整数，如±1、±2等）

需要引入辅助二进制变量来线性化「非零元素计数」的约束：

import cvxpy as cp

n_rows, n_cols = 5, 10  # 示例维度
M = 100  # 足够大的常数，需大于x中元素的最大可能绝对值
x = cp.Variable((n_rows, n_cols), integer=True)
# 辅助二进制变量z_ij：x[i,j]≠0时z_ij=1，否则0
z = cp.Variable((n_rows, n_cols), boolean=True)

constraint2 = []
# 约束1：x[i,j]非零时z_ij必须为1
for i in range(n_rows):
    for j in range(n_cols):
        constraint2.append(cp.abs(x[i,j]) <= M * z[i,j])
# 约束2：每行非零元素数≤1
for i in range(n_rows):
    constraint2.append(cp.sum(z[i, :]) <= 1)

说明 #

• 场景2中的M需要根据实际问题设置为足够大的数值，确保能覆盖x中元素的最大可能绝对值，避免约束失效。
• 两种方法均符合CVXPY的整数规划约束要求，且遵循DCP规则，可被主流整数规划求解器（如Gurobi、CPLEX、GLPK）处理。

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