The Clique Partition Problem with Minimum Clique Size Requirement

Xiaoyun Ji (jixrpi.edu)
John E Mitchell (mitchjrpi.edu)

Abstract: Given a complete graph K = (V , E), with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph K into subcliques that each have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. It is an extension of the classic Clique Partition Problem that can be well solved using triangle inequalities, but the additional size requirement here makes it much harder to solve. The previously known inequalities are not good enough to solve even a small size problem within a reasonable amount of time. In this paper, we'll discuss the polyhedral structure and introduce new kinds of cutting planes: pigeon cutting planes and flower cutting planes. We will report the computational results with a branch-and-cut algorithm confirming the strength of these new cutting planes.

Keywords: clique partition; branch-and-cut; clustering; microaggregation

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. May 2005. http://www.rpi.edu/~mitchj/papers/cppmin.html

Download: [PDF]

Entry Submitted: 05/06/2005
Entry Accepted: 05/06/2005
Entry Last Modified: 05/06/2005

Modify/Update this entry