湖北工业大学学报2022，Vol.37Issue(1) ：29-33.

求解最小支配集的线性混合整型规划算法

A Hybrid Integer Linear Programming Algorithm for Solving the Minimum Dominating Set

程咏锋 吴歆韵 熊才权
湖北工业大学学报2022，Vol.37Issue(1) ：29-33.
✕
  • NETL
  • NSTL
  • 维普
  • 万方数据

求解最小支配集的线性混合整型规划算法

A Hybrid Integer Linear Programming Algorithm for Solving the Minimum Dominating Set

程咏锋 1吴歆韵 1熊才权1
扫码查看

作者信息

  • 1. 湖北工业大学计算机学院,湖北武汉430068
  • 折叠

摘要

提出了一个高效的求解最小支配集问题的线性混合整数规划算法(MILP).该算法主要针对最小支配集问题的特点建立整数规划模型,并通过Gurobi求解器进行优化求解.采用当前国际文献公开的共74个算例作为算法测试实验集,与FKW算法、传统的Grandoni算法以及改进的Grandoni算法进行比较.实验结果表明,该算法的计算效率明显优于其它的精确算法,且在所有算例上都能得到精确解.

关键词

最小支配集/线性整数规划算法/Gurobi求解器/精确算法

引用本文复制引用

基金项目

国家自然科学基金(61902116)

湖北工业大学博士启动基金(BSQD2019022)

出版年

2022
湖北工业大学学报
湖北工业大学

湖北工业大学学报

CHSSCD
影响因子：0.258
ISSN：1003-4684
参考文献量2
段落导航相关论文