1、内点——分支定界法

内点——分支定界法是现代 内点算法和分支定界法结合而成的混合算法 ，能够精确求解离散变量和连续变量同时存在的0 ～1混合整数规划问题。分支定界法能把离散变量的整数规划转化为仅含连续变量的规划问题 ，而内点算法能求解仅含连续变量的规划问题。

随着分支的进行 ，原问题的子问题越来越庞大。为了加快计算速度 ，减少计算量 ，算法对所有子问题进行剪支判断 ，对满足剪支准则的子问题进行剪支 ，不满足准则的子问题进行分支 ，一直到所有分支子问题已经全 部处理完毕 得到问题的最优解。

2、算法流程

基于投资最小配电网扩展规划的数学模型 ，采用内点——分支定界法求解，下面归纳其算法流程 ，如图1所示，为计算流程图。

在图1剪支中，满足以下3个条件可对分支节点进行剪支 ，及时删除不可行的分支 ，减少工作量加快计算速度 ，避免问题收敛于局部最优解。

(1)如果该分支不满足安全约束 ，则该分支问题不可行 ；

(2 )如果所求的目标值最优解f_found满足f_found>f* ε；

(3 )若所求最优解小于f*，则 f*=f_found将其转向条件 b。

如果分支层不满足于上述 3 种情况 ，求解下一个候选分支 ，如果满足则对于不可行子 问题 ，从待分支列队和已经取得子问题队列中删除；对已经得到整数解的松弛子问题从待分支队列中删除，此时已经取得子问题存储整数可行解信息，另外对于为满足整数解要求的松弛子问题加入到待分支队列中。

利用分支定界法求解混合数线性规划时，子一代分支层的目标函数总是大于或等于父代分支层的目标函数。但在混合非线性规划整数规划中，子一代分支层的目标函数不一定总是大于或等于父代分支层的目标函数。为此在条件b中引入了一个安全因子ε，其作用如图2所示。若无ε则nodel节点为最优点，求解陷入局部最优，安全因子ε保证在global点找到全局最优解。