We consider the class of 2-partition inequalities for the clique partitioning problem associated with complete graphs. We propose a heuristic separation algorithm for the inequalities and evaluate its usefulness in a cutting-plane algorithm. Our computational experiments fall into two parts. In the first part, we compare the LP objective values obtained by the proposed separator with those obtained by known separators for 2-partition inequalities and those obtained by exact polynomial-time separators for other classes of inequalities. These results demonstrate the importance of the 2-partition inequalities and the new separator. In the second part of the computational experiments, we apply the separator to different kinds of test instances from the literature. These results show that considerable improvements can be obtained in terms of narrowing the gaps between LP objective values and optimal partition values.
Citation
Dept. of Economics and Business Economics, Aarhus University, Fuglesangs Alle 4, DK-8210 Aarhus V, Denmark. July 2020
Article
View A Separation Heuristic for 2-Partition Inequalities for the Clique Partitioning Problem