一种求解度约束最小生成树问题的混合整数线性规划方法

摘要

针对含有度约束的最小生成树问题,区别于传统启发式算法和智能算法,提出了一种将度约束最小生成树问题线性化的方法。通过邻接矩阵和关联矩阵处理各节点的出线度约束,以电力系统中直流潮流节点功率平衡思想处理网络的辐射性约束,并基于CPLEX平台调用yalmip求解MILP模型。以8节点系统,9节点系统,旅行商问题的eil51系统进行算例测试,证明线性模型能够有效求解含有度约束生成树规划问题。