Al-Ykoob, Salem M.Sherali, Hanif D.2021-01-122021-01-122020-03-230868-4952http://hdl.handle.net/10919/101856This paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems.application/pdfenCreative Commons Attribution 4.0 Internationalgraph partitioningcolumn generationcomplementary column generationmixed-integer programmingArticle - Refereedhttps://doi.org/10.15388/20-INFOR3913111822-8844