|
|||||
|
|
| 基于半定规划的多约束图划分问题 | |
| 引用本文： | 王晓瑜,刘红卫,王婷,丁玉婉,游海龙.基于半定规划的多约束图划分问题[J].吉林大学学报(理学版),2023(3):540-546. |
| 作者姓名： | 王晓瑜 刘红卫 王婷 丁玉婉 游海龙 |
| 作者单位： | 1. 西安电子科技大学数学与统计学院;2. 西安电子科技大学微电子学院 |
| 基金项目： | 广东省重点领域研发计划项目(批准号：2019B010140001)； |
| 摘 要： | 提出一种递归的二分算法，用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型，然后利用超平面舍入算法得到满足顶点权重约束的初始可行解，再进一步设计启发式算法对初始可行划分进行局部改进，以得到更优的划分结果.实验结果表明，所设计的算法可在较短时间内得到多约束图划分问题的高质量解. |
| 关 键 词： | 图划分 半定规划 背包问题 组合优化 |