混合整数规划概述

GNU线性规划工具集（GNU Linear Programming Kit, GLPK）是用来求解大规模之线性规划（LP）、混合整数规划（MIP），跟其他相关问题的软件包。这是一套以ANSI C写的函式库。属于GNU计划的一部分，按GNU通用公共授权条款发行。

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点找到全局最优解。

1、以目标函数为配电网建设的投资费用 (包括新建和改扩建变电站和新建线路) 、配电网网损费用和运行维护费用综合最优的非线性整数规划模型 ，并以严格的数学模型保证配电网辐射结构运行方式。

2、采用内点——分支定界法进行求解。基于广度优先遍历的分支定界法结合原始对偶内点法对大规模的配电网系统进行扩展规划，通过分支节点的剪支，加快计算速度 ，实现了精确求解混合整数规划的全局最优解 。通过算例进行仿真计算 ，得到合理的最优解。但随着系统规模 的增大 ，离散变量的增加使得分支的次数显著增多 ，分支定界法求解子问题的数目急剧增加 ，求解非常耗时 ，这也是分支定界法的一个缺点。基于现代飞速发展的计算机技术，为了解决求解大规模配电网网络重构最优的单机运算耗时巨大的矛盾 ，以达到最佳的优化效果 ，可 以考虑采用并行或是分布式的计算方法 以实现快速和高效地求解全局最优解。 2100433B