大规模最大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 dynamically and searching the auxiliary function. The research achievements can solve large scale max-k-cut problem effectively, and provide enlightenment for other large scale combinatorial optimization problems.

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

最大k割问题是一类经典的组合优化问题，有着广泛的应用背景。随着问题规模的增大，问题的解空间和局部最优解的数量急剧增加。当前的算法容易陷入局部最优解，或求解速度慢。本项目主要针对该问题开展研究，取得了以下主要成果：. 我们研究了最大割问题，设计了几个快速的基于迭代改进的局部搜索算法，提出了一种快速的memetic算法和一种混合粒子群和分布估计算法的交替算法，大大提高了求解速度；研究了大规模最大割问题，设计了全局聚类算法找出精英解的共同结构特征，对图进行聚类，并构造基于收缩图的辅助函数和辅助问题，通过局部搜索算法求解辅助问题找到收缩图的局部最优解，提出了求解大规模最大割问题的离散动态凸化函数算法，实验结果表明，该算法能够在较快时间内找到高质量的解；研究了最大二等分问题，构造了最大二等分问题的辅助问题，并证明了辅助问题与原问题具有相同的全局最优解，提出了一种填充函数算法；提出了求解大规模最大二等分问题的memetic算法，主要包含快速的局部搜索算法、交叉算子、多目标种群更新策略，与著名的circuit算法比较，本算法的求解质量提高了0.02%到4.15%，并且求解时间更短；我们推广离散动态凸化算法来求解组合拍卖竞胜标确定问题，通过一类自适应的罚函数方法将原问题转化为无约束的0-1规划问题，证明了该无约束的0-1规划问题与原问题具有相同的全局最优解和局部最优解，提出了一类求解竞胜标确定问题的离散动态凸化算法，与当前最好的算法比较，本算法能够找到更好的解。同时，我们还研究了最小赋权支配集问题、软硬件划分问题、单行设备布局问题、无线传感网络覆盖问题、集合覆盖问题等。. 在本项目的资助下，课题组共发表学术刊物论文20篇，其中SCI收录刊物论文6篇，EI收录刊物论文4篇。