SCIP库分支定界的边界剪枝机制及MIP初始下界确定方法问询

SCIP的基于边界剪枝完全围绕上下界动态更新与比较展开，核心流程如下：

• 全局上下界初始化：
  • 上界初始设为无穷大，后续通过启发式算法（如贪心、Feasibility Pump、RINS等）找到可行解后，用可行解的目标值更新全局上界。
  • 下界由初始LP松弛计算得到（下文详细说明初始下界确定逻辑）。
• 分支节点的上下界计算：
  • 每个分支节点生成后，先求解该节点子问题的LP松弛，得到当前节点的下界（此下界是该节点所有可能子解的目标值下限）。
  • 同时尝试在该节点上用启发式算法寻找更优可行解，若找到则立即更新全局上界。
• 剪枝判断：
  • 若当前节点的LP松弛下界大于等于全局上界，说明该节点的所有子解目标值不可能优于当前已知最优可行解，直接剪去该节点，停止分支。
  • 这是最基础的剪枝逻辑，SCIP还会结合整数可行性剪枝、强分支剪枝等规则，但基于边界的剪枝是核心。
• 分支递归：
  • 未被剪枝的节点，SCIP会选择一个分数值的整数变量进行分支（如分成x ≥ ceil(x_val)和x ≤ floor(x_val)两个子节点），对每个子节点重复上述计算、更新、判断流程。

SCIP对任意MIP问题的初始下界计算核心依赖LP松弛，并根据问题类型适配处理：

• 标准MIP问题：直接求解原问题的LP松弛（去掉所有整数变量的整数约束，保留线性约束与目标函数），LP松弛的最优目标值即为初始下界。因为LP松弛是原MIP的松弛问题，其最优解目标值一定小于等于原MIP最优解（极小化问题），是可靠的下界。
• 带特殊约束的MIP问题：如含逻辑约束、非线性约束的MINLP，SCIP会先将特殊约束转化为等价线性约束（或线性松弛约束），再求解转化后的LP松弛问题得到初始下界。比如非线性约束会用凸包松弛或线性化技术生成松弛约束，再构建LP模型求解。
• 极端情况处理：若LP松弛不可行，说明原MIP问题也不可行，初始下界设为无穷大；若LP松弛无界，初始下界设为负无穷大（极小化问题），后续通过添加割平面等方式收紧下界。

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