A Complementary Column Generation Approach for the Graph Equipartition Problem
2020; IOS Press; Linguagem: Inglês
10.15388/20-infor391
ISSN1822-8844
AutoresSalem M. Al-Ykoob, Hanif D. Sherali,
Tópico(s)VLSI and FPGA Design Techniques
ResumoThis 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.
Referência(s)