  


The Clique Partition Problem with Minimum Clique Size Requirement
Xiaoyun Ji (jixrpi.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 branchandcut algorithm confirming the strength of these new cutting planes. Keywords: clique partition; branchandcut; 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  