Solving the clique partitioning problem with clique size constraints

Abstract

This thesis considers a clique partitioning problem where the size of cliques is restricted within the prescribed range. This problem is to partition a graph into cliques such that the total sum of the edge weights within each clique is maximized. The problem appears in several applications, including GT cell formation problem, integrated circuit layout problem, and clustering problem, etc. We give a 0-1 integer programming formulation of the problem and use the branch-and-cut approach to solve it. Compared to the traditional branch-and-bound approach, the branch-and-cut approach can save the computational efforts needed to solve hard combinatorial optimization problems by embedding strong cutting planes within the branch-and-bound scheme. We used some valid inequalities for the convex hull of the integral feasible solutions of the problem as cutting planes. The algorithm was tested on several randomly generated problems and real-world problems found in the literature.