×

New facets and a branch-and-cut algorithm for the weighted clique problem. (English) Zbl 1099.90068

Summary: 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.

MSC:

90C35 Programming involving graphs or networks
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dijkhuizen, G.; Faigle, U., A cutting-plane approach to the edge-weighted maximal clique problem, European Journal of Operational Research, 69, 121-130 (1993) · Zbl 0787.90059
[2] Faigle, U.; Garbe, R.; Heerink, K.; Spieker, B., LP-relaxations for the edge-weighted subclique problem, (Bachem, A.; Derigs, U.; Jünger, M.; Schrader, R., Operations Research ’93 (1994), Physica-Verlag: Physica-Verlag Heidelberg), 157-160
[3] Grötschel, M.; Wakabayashi, Y., A cutting plane algorithm for a clustering problem, Mathematical Programming, 45, 59-96 (1989) · Zbl 0675.90072
[4] M. Hunting, Relaxation Techniques for Discrete Optimization Problems-Theory and Algorithms, Ph.D. thesis, University of Twente, 1998; M. Hunting, Relaxation Techniques for Discrete Optimization Problems-Theory and Algorithms, Ph.D. thesis, University of Twente, 1998
[5] Hunting, M.; Faigle, U.; Kern, W., A Lagrangian relaxation approach to the edge-weighted clique problem, European Journal of Operational Research, 131, 119-131 (2001) · Zbl 1039.90044
[6] Johnson, E. L.; Mehrotra, A.; Nemhauser, G. L., Min-cut clustering, Mathematical Programming, 62, 133-151 (1993) · Zbl 0807.90117
[7] Macambira, E. M.; de Souza, C. C., The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations, European Journal of Operational Research, 123, 346-371 (2000) · Zbl 0961.90067
[8] Mehrotra, A., Cardinality constrained Boolean quadratic polytope, Discrete Applied Mathematics, 79, 137-154 (1997) · Zbl 0898.90092
[9] Padberg, M., The Boolean quadric polytope: Some characteristics, facets and relatives, Mathematical Programming, 45, 139-172 (1989) · Zbl 0675.90056
[10] Park, K.; Lee, K.; Park, S., An extended formulation approach to the edge-weighted maximal clique problem, European Journal of Operational Research, 95, 671-682 (1996) · Zbl 0926.90086
[11] Sherali, H. D.; Lee, Y.; Adams, W. P., A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, Operations Research Letters, 17, 19-26 (1995) · Zbl 0835.90080
[12] M.M. Sørensen, \(b\); M.M. Sørensen, \(b\)
[13] M.M. Sørensen, New facets and a branch-and-cut algorithm for the weighted clique problem, Working paper 01-2, Department of Management Science and Logistics, The Aarhus School of Business, 2001(Available at www.asb.dk/ mim/papers.htm; M.M. Sørensen, New facets and a branch-and-cut algorithm for the weighted clique problem, Working paper 01-2, Department of Management Science and Logistics, The Aarhus School of Business, 2001(Available at www.asb.dk/ mim/papers.htm
[14] Späth, H., Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs, Zeitschrift für Operations Research, 29, 125-131 (1985) · Zbl 0581.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.