添加约束后MILP由不可行变可行？CBC求解器技术咨询

以下是几种常见的实际原因：

• 整数可行性容差与数值精度问题
  CBC求解器默认的整数可行性容忍度（如integerTolerance参数）有一定阈值，若你的模型约束中存在浮点数系数、或变量取值的计算存在微小数值偏差，求解器可能会误判原本满足约束的可行解为不满足。添加var_1 == var_2这条整数等式约束后，不仅缩小了搜索空间，还因为该约束的数值关系绝对明确，帮求解器避开了精度模糊的判定区间，从而成功识别到可行解。

• 分支定界的过早剪枝
  当变量数量较多、且整数变量取值范围（[1,50]）较宽时，整个问题的搜索空间会呈指数级膨胀。CBC的分支定界算法会基于启发式规则剪枝掉一些看似无前景的分支，但可能误剪掉了包含可行解的分支，最终返回“无可行解”。添加var_1 == var_2后，搜索空间被大幅压缩，求解器无需遍历过多分支即可定位到可行解所在的子空间。

• 启发式搜索的引导缺失
  CBC默认的启发式搜索策略在某些特定模型结构下，可能难以快速定位到可行解。而你添加的约束恰好属于已知可行解的一部分，相当于给求解器提供了明确的搜索引导，让启发式算法能更快找到满足所有约束的变量组合。

• 模型约束的隐性表述问题
  若你手动验证的可行解确实满足所有约束，可能模型中存在一些隐性的表述错误（比如约束符号写反、系数计算错误），但该错误恰好被var_1 == var_2的约束抵消，使得修正后的模型能正确找到可行解。这种情况需仔细核对模型的约束逻辑与代码实现。

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