MATLAB分支定界法：整数规划求解源码解析

本文档是一份名为“【老生谈算法】MATLAB分支定界法程序源码”的文档，它提供了使用MATLAB实现的整数线性规划（Integer Linear Programming, ILP）分支定界法的详细程序代码。分支定界法是一种用于解决混合整数优化问题的有效算法，适用于那些目标函数和约束条件都是线性的，并且包含整数变量的情况。 该函数`ILp`的功能是求解纯整数规划或混合整数规划问题，通过最小化目标函数`f' * x`，满足一系列线性不等式`G * x <= h`和等式`Geq * x = heq`。输入参数包括： 1. 目标函数系数向量`f` 2. 线性不等式系数矩阵`G`和右侧常数向量`h` 3. 线性等式系数矩阵`Geq`和等号右侧常数向量`heq` 4. 解的下界列向量`lb`（默认为整数型） 5. 解的上界列向量`ub`（默认也为整数型） 6. 初始迭代点`x`（默认为空） 7. 整数变量指标向量`id`（1表示整数，0表示实数，默认为全为1） 8. 选项参数`options`（用于控制算法行为，默认为无显示输出） 在`ILp`函数中，首先检查输入参数的完整性并设置默认值，然后调用内部子函数`ILP`进行实际的优化。`ILP`函数利用MATLAB的`linprog`函数，对当前的变量范围`vlb`和`vub`进行线性规划求解。如果找到一个更好的解，即`ftemp`（新的最优目标函数值）小于当前的上界`upper`，则更新最优解`x`和`upper`。 为了防止数值误差，程序设置了两个阈值：0.00005，当`ftemp`与`upper`的差小于这个值，或者`x`中的整数部分与`round(x.*ID)`接近时，认为找到了一个满意的近似解，不再继续搜索。 这份MATLAB代码提供了一个完整的分支定界算法实现框架，适合在处理整数线性优化问题时调用，特别是对于混合整数问题，它能够有效地进行分支和剪枝操作，以逐步缩小问题的搜索空间，直至找到全局最优解。