| 求解最大割问题的分枝定界算法 |
| |
| 引用本文： | 张亚玲,龙熙华,穆学文.求解最大割问题的分枝定界算法[J].西安科技大学学报,2006,26(4):541-544. |
| |
| 作者姓名： | 张亚玲 龙熙华 穆学文 |
| |
| 作者单位： | 1. 西安科技大学,计算机系,陕西,西安,710054
2. 西安电子科技大学,应用数学系,陕西,西安,710071 |
| |
| 摘 要： | 最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在谈模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解，是求解中小规模最大割问题的有效方法。
|
| 关 键 词： | 最大割问题 二次规划 分枝定界 |
| 文章编号： | 1672-9315(2006)04-0541-04 |
| 修稿时间： | 2005年10月30 |
The branch-and-bound algorithm for max-cut problem |
| |
| ZHANG Ya-ling,LONG Xi-hua,MU Xue-wen.The branch-and-bound algorithm for max-cut problem[J].JOurnal of XI’an University of Science and Technology,2006,26(4):541-544. |
| |
| Authors: | ZHANG Ya-ling LONG Xi-hua MU Xue-wen |
| |
| Abstract: | The max-cut problem is a standard NP-hard problem in graph graphic theory.Based on semidefinite programming relaxation model of the max-cut problem,a quadratic programming relexation model is presented.We have proven that quadratic programming relexation model is better than the semidefinite programming relaxation model in theory.Based on the model,we use the Branch-and-Bound algorithm to solve the max-cut problem.Numerical results for the small scale problems and the middle scale problems demonstrate that a better solution can be obtained by the algorithm,and the algorithm is an effective algorithm for the max-cut problem with a middle scale. |
| |
| Keywords: | max-cut problem quadratic programming branch-and-Bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
