Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement |
| |
Authors: | Xiaoyun Ji John E Mitchell |
| |
Institution: | aDepartment of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA |
| |
Abstract: | Given a complete graph Kn=(V,E)with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph Kn into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this paper, we consider using the branch-and-price method to solve the problem. We demonstrate the necessity of cutting planes for this problem and suggest effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present computational results on large randomly generated problems. |
| |
Keywords: | Graph partition branch-and-price clustering micro-aggregation |
本文献已被 ScienceDirect 等数据库收录! |