Lagrangian relaxation and pegging test for the clique partitioning problem
Lagrangian relaxation and pegging test for the clique partitioning problem
复制标题
DOI：
10.1007/s11634-013-0135-5
复制
发表时间：
2013-05
影响因子：
1.6
通讯作者：
Noriyoshi Sukegawa;Yoshitsugu Yamamoto;Liyuan Zhang
中科院分区：
文献类型：
--
作者：
Noriyoshi Sukegawa;Yoshitsugu Yamamoto;Liyuan Zhang
团划分问题是一个NP-难的组合优化问题，在数据分析中有着广泛的应用，如聚类分析。虽然二进制整数线性规划公式已经知道了很多年，但在解决大型实例时需要处理大量的变量和约束。本文提出了一种基于拉格朗日松弛和钉住检验的尺寸缩减算法，并通过数值实验验证了其有效性。我们修改了传统的次梯度方法，以管理的拉格朗日乘子的高维，并利用集团划分问题的结构特性，对普通的钉住测试也作出了改进。
The clique partitioning problem is anNP-hard combinatorial optimization problem with applications to data analysis such as clustering. Though a binary integer linear programming formulation has been known for years, one needs to deal with a huge number of variables and constraints when solving a large instance. In this paper, we propose a size reduction algorithm which is based on the Lagrangian relaxation and the pegging test, and verify its validity through numerical experiments. We modify the conventional subgradient method in order to manage the high dimensionality of the Lagrangian multipliers, and also make an improvement on the ordinary pegging test by taking advantage of the structural property of the clique partitioning problem.