如何限制CP-SAT求解器输出的非零weight数量并维持分布约束？

给定如下数据集：

需求为重新分配weights列的值，需满足：

1. 维持id、class、country各唯一值的权重总和分布（允许±5%误差）
2. 输出结果中仅包含指定数量的非零weight值（例如仅3个非零值，其余为0）

核心思路 #

通过引入二进制辅助变量标记每行是否保留非零权重，再约束二进制变量的总和来控制非零值数量，同时关联二进制变量与权重的取值逻辑，结合原有总和约束完成求解。

具体步骤（以PuLP求解器为例） #

假设你已实现基础的线性规划模型，现在添加以下约束：

1. 定义变量
   给每行定义两个变量：一个表示新权重（非负），一个表示该行是否为非零权重（二进制0/1）

   import pulp
   df = ... # 你的原始数据集
   model = pulp.LpProblem("Weight_Allocation", pulp.LpMinimize) # 可根据需求选择最大化
   
   # 定义权重变量，取值非负
   new_weights = pulp.LpVariable.dicts("new_weight", df.index, lowBound=0)
   # 定义二进制变量，标记是否非零
   is_non_zero = pulp.LpVariable.dicts("is_non_zero", df.index, cat="Binary")
   

2. 关联二进制变量与权重
   确保当二进制变量为0时，权重必须为0；为1时权重可正常取值。这里用一个足够大的M值（取略大于原始总权重的数值）来实现约束：

   M = df['weights'].sum() * 1.05 # 取略大于总权重的安全值
   for idx in df.index:
       model += new_weights[idx] <= M * is_non_zero[idx]
   

3. 限制非零值数量
   添加约束，让所有二进制变量的总和等于你指定的数量（比如3）：

   target_non_zero_count = 3
   model += pulp.lpSum(is_non_zero[idx] for idx in df.index) == target_non_zero_count
   

4. 保留原有总和约束
   继续保留你之前实现的id、class、country权重总和误差约束，示例如下：

   # id维度的总和约束（允许±5%误差）
   id_total = df.groupby('id')['weights'].sum()
   for id_val in id_total.index:
       min_sum = id_total[id_val] * 0.95
       max_sum = id_total[id_val] * 1.05
       model += pulp.lpSum(new_weights[idx] for idx in df[df['id'] == id_val].index) >= min_sum
       model += pulp.lpSum(new_weights[idx] for idx in df[df['id'] == id_val].index) <= max_sum
   
   # 同理添加class、country维度的总和约束
   

5. 求解并提取结果
   执行求解后，将结果映射回数据集：

   model.solve()
   df['new_weights'] = [pulp.value(new_weights[idx]) for idx in df.index]
   

注意事项 #

• M值需合理选择，既要大于单一行可能的最大权重，又不能过大影响求解效率
• 若指定的非零数量过小，可能导致模型无解，此时需调整目标数量或放宽误差范围
• 其他求解器（如Gurobi、CPLEX）逻辑一致，仅变量定义和约束语法略有差异

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