Optimization Online


The Clique Partition Problem with Minimum Clique Size Requirement

Xiaoyun Ji (jix***at***rpi.edu)
John E Mitchell (mitchj***at***rpi.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society