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

G.C. van Dijkhuizen, U. Faigle

Research output: Contribution to journalArticleAcademicpeer-review

30 Citations (Scopus)
91 Downloads (Pure)

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.
Original languageUndefined
Pages (from-to)121-130
Number of pages10
JournalEuropean journal of operational research
Volume69
Issue number1
DOIs
Publication statusPublished - 1993

Keywords

  • Clique polytope
  • Cutting plane
  • METIS-140748
  • Partition polytope
  • IR-30109
  • Integer linear programming

Cite this