分支定界（branch and bound）思想及其代码实现思路（附带Java Cplex代码讲解）

Answer 1

分支定界思想在解决整数规划（IP）和混合整数规划（MIP）问题中扮演核心角色，许多商业求解器如Cplex和Gurobi等都以此为设计框架。IP领域的基础算法，分支定界思想也是分支定价（branch and price）和分支定价切割（branch and price and cut）算法的基石。

算法逻辑分为两部分：分支与定界。解决MIP问题时，首先通过松弛操作，移除整数限制，将问题转化为线性规划（LP）。假设处理最小值（min）问题，使用Simplex法求解得到初始LP目标函数作为下界（lower bound）。如果有一个整数可行解，其目标函数作为上界（upper bound）。

获取上界过程，是在LP基础上添加整数割，缩小解空间。IP与LP目标相同，解空间更大的模型通常能提供更好的解。因此，上界始终小于等于下界。

分支定界的本质是构建搜索树，根节点为原始LP问题，通过分支策略递归分解为子问题。搜索树采用广度优先搜索（BFS）或深度优先搜索（DFS）探索，不断更新上界。初始时，下界与上界差距最大，随着搜索进行，找到更优整数解缩小差距，接近最优解。

分支策略将MIP问题分解成互斥或非互斥子问题以求解整数解。例如，若变量值为非整数，可添加整数割进行分支。不同建模问题采用不同分支方法，如VRPTW模型分支策略参见相关论文。

剪支策略在搜索树中剪掉不产生更好解的分支，减少搜索时间。通常在发现分支不可行或当前节点LP值大于已知最优整数解时执行剪支。

迭代停止准则包括基于gap值判断或搜索树空时停止。当gap值足够小或搜索树遍历完毕，即找到最优或近似最优解。

Java与Cplex结合实现分支定界代码流程：首先解析问题数据，使用类封装建模及求解步骤。分支和定界框架包含属性如搜索栈、上界、最优解、模型数据、已访问状态等。遍历搜索树，对节点进行处理：求解、剪支、更新上界。代码逻辑清晰，关键在于理解分支定界思想，掌握分支、搜索节点、上下界更新方法。使用BFS只需将栈替换为队列，实现方式与DFS相同。