Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

New facets and a branch-and-cut algorithm for the weighted clique problem

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • 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 use these inequalities 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.
Udgivelsesdato: APR 1
OriginalsprogEngelsk
TidsskriftEuropean Journal of Operational Research
Vol/bind154
Nummer1
Sider (fra-til)57-70
Antal sider14
ISSN0377-2217
StatusUdgivet - 2004

    Forskningsområder

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

Se relationer på Aarhus Universitet Citationsformater

ID: 32322737