column generation场景下基于CPLEX的新增列reduced cost校验问题

1. reduced cost符号异常修复 #

最大化问题的reduced cost计算逻辑与默认最小化场景相反，参考帖的默认计算逻辑适配最小化问题，直接复用会导致符号恒负。
CPLEX侧正确校验新增列reduced cost的流程：

• 调用CPXgetpi()获取主问题所有约束的对偶值，确保行索引与建模时约束顺序完全一致
• 最大化场景下reduced cost计算公式：reduced_cost = 新增列目标系数 - sum(对偶值[i] * 新增列在第i个约束的系数)
• 未将新增列加入主问题并完成优化前，不要调用CPXgetrc()查询reduced cost，CPLEX会默认将未入基变量按最小化规则补符号，导致结果异常

2. 正reduced cost列加入后目标值不提升排查项 #

• 校验定价子问题目标方向：最大化主问题对应的定价子问题目标为最大化（新增列目标系数 - sum(对偶值 * 新增列约束系数)），目标方向写反会导致生成的列实际reduced cost为负，无法提升目标值
• 校验列入注逻辑：确认调用CPXaddcols()时，新增列的约束系数、目标系数的取值与顺序完全正确，无符号写反、索引错位问题
• 校验主问题优化方向：确认已调用CPXsetobjsen(env, lp, CPX_MAX)设置最大化目标，CPLEX默认优化方向为最小化，方向错配会导致加列无收益
• 校验列重复性：若新增列与主问题已有列线性相关，加入后基矩阵无变化，目标值不会提升，可在加列前新增重复列过滤逻辑

3. 快速验证方案 #

手动选取1个已知可提升主问题目标值的有效列，代入上述reduced cost公式计算，与代码输出结果比对，可快速定位是reduced cost计算逻辑错误还是定价子问题生成逻辑错误。 #

内容的提问来源于stack exchange，提问作者Nguyen Quang Anh