A CUTTING-PLANE APPROACH TO THE EDGE-WEIGHTED MAXIMAL CLIQUE PROBLEM

We investigate the computational performance of a cutting-plane algori thm for the problem of determining a maximal subclique in an edge-weig hted complete graph. Our numerical results are contrasted with reports on closely related problems for which cutting-plane approaches perfor m well in instances of moderate size. Somewhat surprisingly, we find t hat our approach already in the case of n = 15 or n = 25 nodes in the underlying graph typically neither produces an integral solution nor y ields a good approximation to the true optimal objective function valu e. This result seems to shed some doubt on the universal applicability of cuttingplane approaches as an efficient means to solve linear (0, 1)-programming problems of moderate size.