基于半定规划的多约束图划分问题

吉林大学学报(理学版) ›› 2023, Vol. 61 ›› Issue (3): 540-546.

基于半定规划的多约束图划分问题

王晓瑜¹, 刘红卫¹, 王婷¹, 丁玉婉¹, 游海龙²

1. 西安电子科技大学数学与统计学院, 西安 710126； 2. 西安电子科技大学微电子学院, 西安 710071

收稿日期:2022-06-11 出版日期:2023-05-26 发布日期:2023-05-26
通讯作者: 刘红卫 E-mail:hwliuxidian@163.com

Multi-constraint Graph Partitioning Problem Based on Semidefinite Programming

WANG Xiaoyu¹, LIU Hongwei¹, WANG Ting¹, DING Yuwan¹, YOU Hailong²

1. School of Mathematics and Statistics, Xidian University, Xi’an 710126, China；
2. School of Microelectronics, Xidian University, Xi’an 710071, China

Received:2022-06-11 Online:2023-05-26 Published:2023-05-26

摘要/Abstract

摘要： 提出一种递归的二分算法, 用于求解带顶点权重约束的图划分问题. 首先利用内点法求解不加顶点权重约束的半定规划松弛模型, 然后利用超平面舍入算法得到满足顶点权重约束的初始可行解, 再进一步设计启发式算法对初始可行划分进行局部改进, 以得到更优的划分结果. 实验结果表明, 所设计的算法可在较短时间内得到多约束图划分问题的高质量解.

关键词: 图划分, 半定规划, 背包问题, 组合优化

Abstract: We proposed a recursive dichotomy algorithm to solve the graph partitioning problem with vertex weight constraint. Firstly, the interior point method was used to solve the semidefinite programming relaxation model without vertex weight constraint. Secondly, the initial feasible solution satisfying the vertex weight constraint was obtained by hyperplane rounding algorithm. Thirdly, the heuristic algorithm was further designed to locally improve the initial feasible partition to obtain the optimal partition result. The experimental results show that the proposed algorithm can obtain the high quality solution to the multi-constraint graph partitioning problem in a short time.

Key words: graph partitioning, semidefinite programming, knapsack problem, combinatorial optimization

中图分类号:

O221.7

王晓瑜, 刘红卫, 王婷, 丁玉婉, 游海龙. 基于半定规划的多约束图划分问题[J]. 吉林大学学报(理学版), 2023, 61(3): 540-546.

WANG Xiaoyu, LIU Hongwei, WANG Ting, DING Yuwan, YOU Hailong. Multi-constraint Graph Partitioning Problem Based on Semidefinite Programming[J]. Journal of Jilin University Science Edition, 2023, 61(3): 540-546.

[1]	隋振, 张天星, 吴涛, 陈华锐. 基于多种群空间映射遗传算法的立体仓库储位优化[J]. 吉林大学学报(理学版), 2022, 60(1): 127-0134.
[2]	杨雪, 董红斌, 董宇欣. 改进的量子粒子群优化算法对多维多选择背包问题的求解[J]. 吉林大学学报(理学版), 2018, 56(6): 1461-1468.
[3]	任维武, 张波辰, 底晓强, 卢奕南. 基于人工蜂群优化的密度聚类异常入侵检测算法[J]. 吉林大学学报(理学版), 2018, 56(1): 95-100.
[4]	于连江, 吴春国, 郭立强, 梁艳春, 杨锌朔. 易物模型及其求解算法[J]. J4, 2010, 07(4): 653-657.
[5]	关凇元, 刘大有, 金弟, 王新华, 苏奎. 基于局部搜索的遗传算法求解自动组卷问题[J]. J4, 2009, 47(05): 961-968.
[6]	黄岚，王康平，周春光，庞巍，董龙江, 彭利. 粒子群优化算法求解旅行商问题[J]. J4, 2003, 41(04): 477-480.
[7]	黄岚　王康平　周春光　原媛　庞巍. 基于蚂蚁算法的混合方法求解旅行商问题[J]. J4, 2002, 40(04): 369-373.