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

摘要

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