Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

New Facets and a Branch-and-Cut Algorithm for the Weighted Clique Problem

Publikation: Working paperForskning

  • Erhvervsøkonomisk Institut
  • CORAL - Centre for Operations Research Applications in Logistics
We consider a polyhedral approach to the weighted maximal b-clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce four new classes of facet defining inequalities for the associated b-clique polytope. One of these inequality classes constitutes a generalization of the well known tree inequalities; the other classes are associated with multistars. We utilize these inequality classes together with other classes of facet defining inequalities in a branch-and-cut algorithm for the problem. We give a description of this algorithm, including some separation procedures, and present the computational results for different sets of test problems. The computation times that are obtained indicate that this algorithm is more efficient than previously described algorithms for the problem.
StatusUdgivet - 2001


  • Combinatorial optimization, Boolean quadratic problem, Edge-weighted clique problem, Maximum dispersion problem, Polyhedra, HHÅ forskning

Se relationer på Aarhus Universitet Citationsformater

ID: 32301901