[1]程咏锋,吴歆韵,熊才权.求解最小支配集的线性混合整型规划算法[J].湖北工业大学学报,2022,(1):29-33.
　CHENG Yongfeng,WU Xinyun,XIONG Caiquan. A Hybrid Integer Linear Programming Algorithm for Solving the Minimum Dominating Set[J].,2022,(1):29-33.
点击复制

求解最小支配集的线性混合整型规划算法()
分享到：

《湖北工业大学学报》[ISSN:1003-4684/CN:42-1752/Z]

卷:
期数:
2022年第1期
页码:
29-33
栏目:
湖北工业大学学报
出版日期:
2022-02-28

文章信息/Info

Title:
 A Hybrid Integer Linear Programming Algorithm for Solving the Minimum Dominating Set
文章编号:
1003-4684(2022)01-0029-05
作者:
程咏锋;  吴歆韵;  熊才权
湖北工业大学计算机学院， 湖北 武汉 430068
Author(s):
 CHENG Yongfeng; WU Xinyun; XIONG Caiquan
 School of Computer Science, Hubei Univ. of Tech., Wuhan 430068, China
关键词:
最小支配集;  线性整数规划算法;  Gurobi求解器;  精确算法
Keywords:
 ; minimum dominating set;  linear integer programming algorithm;  gurobi solver;  exact algorithm
分类号:
TP30
文献标志码:
A
摘要:
提出了一个高效的求解最小支配集问题的线性混合整数规划算法（MILP）。该算法主要针对最小支配集问题的特点建立整数规划模型，并通过Gurobi求解器进行优化求解。采用当前国际文献公开的共74个算例作为算法测试实验集，与FKW算法、传统的Grandoni算法以及改进的Grandoni算法进行比较。实验结果表明，该算法的计算效率明显优于其它的精确算法，且在所有算例上都能得到精确解。
Abstract:
 An efficient linear mixed integer programming algorithm (MILP) for solving the minimum dominating set problem is proposed. The algorithm mainly establishes an integer programming model based on the characteristics of the minimum dominating set problem, and optimizes it through the Gurobi solver. A total of 74 calculation examples published in the current international literature are used as the algorithm test experiment set to compare with the FKW algorithm, the traditional Grandoni algorithm and the improved Grandoni algorithm. Experimental results show that the computational efficiency of this algorithm is significantly better than other accurate algorithms, and accurate solutions can be obtained on all calculation examples.

参考文献/References:

[1] SHEN C, LI T. Multi-document summarization via the minimum dominating set[C]∥International Conference on Computational Linguistics(ICCL).IEEE， 2010,20-22.
[2] DINH T N, SHEN Y, NGUYEN D T. On the approximability of positive influence dominating set in social networks[J]. Journal of Combinatorial Optimization， 2014,27(3): 487-503.
[3] CHENG X,MIN D,DU D H,et al.Virtual backbone construction in multihop ad hoc wireless[J] networks.Wireless Communications & Mobile Computing， 2010,6(2): 183-190.
[4] FOMIN F V, KRATSCH D, WOEGINGER G J. Exact (exponential) algorithms for the dominating set problem[J]. Lecture Notes in Computer Science， 2004,3353: 245-256.
[5] GRANDONI F. A note on the complexity of minimum dominating set[J]. Journal of Discrete Algorithms， 2006,4(2): 209-214.
[6] 路纲,周明天,唐勇,等.任意图支配集精确算法回顾[J].计算机学报， 2010,33(6): 1073-1087.
[7] HEDAR A-R, ISMAIL R. Hybrid genetic algorithm for minimum dominating set problem[C]∥International conference on computational science and its applications: Springer, 2010,457-467.
[8] POTLURI A, SINGH A. Two hybrid meta-heuristic approaches for minimum dominating set problem[C]∥ International Conference on Swarm, Evolutionary, and Memetic Computing: Springer, 2011,97-104.
[9] CHALUPA D. An order-based algorithm for minimum dominating set with application in graph mining[J]. Information Sciences， 2018,426: 101-116.
[10] ZHU X, WANG W, SHAN S, et al. A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs[J]. Journal of Combinatorial Optimization，2012,23(4): 443-450.
[11] 袁福宇. 若干支配集优化问题求解的方法研究[D]. 长春: 东北师范大学, 2019.
[12] SIMONETTI L, CUNHA A, LUCENA A. The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm[C]∥International Conference on Network Optimization, 2011,34-37
[13] GENDRON B, LUCENA A, DA CUNHA A S,et al. Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem[J]. INFORMS Journal on Computing， 2014,26(4): 645-657.
[14] 王灵敏, 周淘晴, 吴歆韵, 等. 求解最小连通支配集问题的变深度邻域搜索算法[J]. 中国科学:信息科学，2016(4): 445-460.
[15] JOVANOVIC R, TUBA M. Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem[J]. Computer Science & Information Systems， 2013,10(1): 133-149.
[16] RUTGERS.Coloring problems dimacs graph formate[EB/OL].[2019-01-15]. Coloring Problems: DIMACS Graph Format (free.fr).

相似文献/References:

[1]吴歆韵,彭　瑞,熊才权.求解最小支配集问题的禁忌遗传混合算法[J].湖北工业大学学报,2024,39(2):17.
　WU Xinyun,PENG Rui,XIONG Caiquan.Hybrid Tabu Search and Genetic Algorithm for Solving Minimum Dominating Set Problem[J].,2024,39(1):17.

备注/Memo

备注/Memo:
［收稿日期］ 2021-07-23
［基金项目］ 国家自然科学基金（61902116）； 湖北工业大学博士启动基金（BSQD2019022）
［第一作者］ 程咏锋（1995-），男，湖北黄冈人，湖北工业大学硕士研究生，研究方向为计算机科学与技术
［通信作者］ 吴歆韵（1987-），男，江苏丹阳人，工学博士，湖北工业大学副教授，研究方向为组合优化算法
更新日期/Last Update: 2022-02-25