大规模最大k割问题的离散动态凸化算法研究

项目名称： 大规模最大k割问题的离散动态凸化算法研究

项目编号： No.11301255

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 林耿

作者单位： 闽江学院

项目金额： 23万元

中文摘要： 最大k割问题是一类最基本的组合优化问题。它是NP困难的，并且有着广泛的应用背景。大规模最大k割问题的解空间巨大，拥有很多的局部最优解。现有的方法求解速度较慢，或者容易陷入局部最优解。本项目研究快速求解大规模最大k割问题的有效方法。首先，分析图的拓扑结构，研究图的局部聚类的近似算法，有效降低问题的规模并保证聚类后收缩图的质量。构造基于迭代改进的局部搜索算法，搜索图的局部最优解。其次，通过分析先前找到的局部最优解的共同结构特征，构造全局聚类算法，对图进行重新聚类。然后，利用局部搜索算法划分收缩图，构造带单个参数的辅助函数，减少局部最优解的数目，设计离散动态凸化算法，通过动态调整参数和搜索辅助函数寻找更好的局部最优解。本项目的研究成果不仅能够有效求解大规模最大k割问题，而且对解决其它大规模组合优化问题有借鉴作用。

中文关键词： 最大K割；离散动态凸化算法；聚类；启发式算法；局部搜索

英文摘要： The max-k-cut problem is one of the most basic combinatorial optimization problems. It is NP hard, and has many applications. The large scale max-k-cut problem has a huge solution space, and a lot of local optimal solutions. Existing methods solve the problem slowly, or get stuck in local optimal solutions easily. This project aims to develop a fast and efficient solution approach for solving the large scale max-k-cut problem. Firstly, the proposed approach analyses the topological structure of graph, and studies an approximation algorithm for local clustering. The local clustering algorithm reduces the scale of the problem effectively, and insures the quality of the clustered graph. An iterative improvement local search algorithm is presented to find local optimal solutions. Next, a global clustering algorithm is constructed by analysing the common structures of the previously found local optimal solutions，and the graph is clustered by the global clustering algorithm. Then, the proposed approach uses the local search algorithm for the clustered graph to find local optimal solutions, and constructes an auxiliary function with a single parameter,the number of local optimal solutions decreases. A discrete dynamic convexized method is proposed to find better local optimal solutions by adjusting the parameter dynami

英文关键词： max-k-cut；discrete dynamic convexized method；clustering；heuristic；local search