A cutting-plane approach to the edge-weighted maximal clique problem

The authors investigate the computational performance of a cutting-plane algorithm for the problem of determining a maximum subclique in an edge-weighted complete graph. The present numerical results are contrasted with reports on closely related problems for which cutting-plane approaches perform well in instances of moderate size. Somewhat surprisingly, the authors find that their approach already in the case of n=15 or n=25 nodes in the underlying graph typically neither produces an integral solution nor yields a good approximation of te true optimal objective function value. 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.