摘要

研究了带有顶点权重约束的图划分问题.首先基于矩阵的提升将原问题转化为半定规划松弛模型,利用半定规划内点法求解该模型,并在求解过程中给出了具体的初始点选取策略和步长选取策略.随后利用改进的随机超平面舍入算法和2opt启发式算法求得原问题的近似最优解.数值实验表明该文的算法可有效求解带有顶点权重约束的图划分问题,且对于稀疏图的求解表现出了良好的性能.