图的最大二等分问题的秩二松弛算法的改进

摘要：

本文在吸取半定规划松弛和秩二松弛方法的优点,克服其缺点的基础上,针对模型目标函数非凸的特点,提出了图的最大二等分问题的秩二松弛模型.由于该模型变量的数目没有增加,因此该方法对求解大规模问题很有优势.数值实验表明,这种算法无论是与半定规划松弛还是原秩二松弛算法相比,在获得目标函数值相当的情况下,运行时间较短.

关键词：图的最大二等分问题、秩二松弛、拟Newton法

所属期刊栏目：27

分类号：O221.2(运筹学)

在线出版日期：2010-09-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：621-626