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

Dijkhuizen van, G. and Faigle, U. (1993) A cutting-plane approach to the edge-weighted maximal clique problem. European Journal of Operational Research, 69 (1). pp. 121-130. ISSN 0377-2217

Preview

PDF
747Kb

Abstract:	We investigated the computational performance of a cutting-plane algorithm for the problem of determining a maximal subclique in an edge-weighted complete graph. Our numerical results are contrasted with reports on closely related problems for which cutting-plane approaches perform well in instances of moderate size. Somewhat surprisingly, we find that our 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 to the 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.
Item Type:	Article
Copyright:	© 1993 Elsevier Science
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS) Management and Governance (SMG)
Research Chair:	Operations Management and Logistics (OMPL)
Research Group:	Industrial Engineering & Business Information Systems (IEBIS)
Link to this item:	http://purl.utwente.nl/publications/30109
Official URL:	http://dx.doi.org/10.1016/0377-2217(93)90097-7
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140748