Cutting-Plane Approach to the Edge-Weighted Maximal Clique Problem

摘要

The computational performance of a cutting plane algorithm for the problem ofdetermining a maximal subclique in an edge weighted complete graph is investigated. The numerical results are contrasted with reports on closely related problems for which cutting plane approaches perform well in instances of moderate size. The approach in the case of n = 15 or n = 25 nodes in the underlying graph typically produces neither an integral solution nor yields a good approximation to the true optimal objective function value. This result seems to shed some serious doubt on the universal applicability of cutting plane approaches as an efficient means to solve linear (0,1) programming problems of moderate size.