|
|||||
|
|
| 带有顶点权重约束的图划分问题研究 | |
| 引用本文： | 丁玉婉,刘红卫,王婷,王晓瑜,游海龙.带有顶点权重约束的图划分问题研究[J].哈尔滨师范大学自然科学学报,2023(1):35-42. |
| 作者姓名： | 丁玉婉 刘红卫 王婷 王晓瑜 游海龙 |
| 作者单位： | 西安电子科技大学 |
| 基金项目： | 广东省重点领域研发计划资助(2019B010140001)； |
| 摘 要： | 研究了带有顶点权重约束的图划分问题.首先基于矩阵的提升将原问题转化为半定规划松弛模型，利用半定规划内点法求解该模型，并在求解过程中给出了具体的初始点选取策略和步长选取策略.随后利用改进的随机超平面舍入算法和2opt启发式算法求得原问题的近似最优解.数值实验表明该文的算法可有效求解带有顶点权重约束的图划分问题，且对于稀疏图的求解表现出了良好的性能. |
| 关 键 词： | 图划分 半定规划 内点法 随机超平面舍入算法 组合优化 |