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

DOI10.1016/S0377-2217(02)00852-4zbMath1099.90068OpenAlexW2044024461MaRDI QIDQ1420411

Michael Malmros Sørensen

Publication date: 2 February 2004

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00852-4

zbMATH Keywords

Combinatorial optimizationproblemPolyhedraBoolean quadratic problemEdge-weighted cliqueMaximum dispersion problem

Mathematics Subject Classification ID

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

Related Items (23)

A new family of facet defining inequalities for the maximum edge-weighted clique problem ⋮ The Boolean Quadric Polytope ⋮ A review on algorithms for maximum clique problems ⋮ Iterated tabu search for the maximum diversity problem ⋮ When centers can fail: a close second opportunity ⋮ Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances ⋮ Solving the maximum edge weight clique problem via unconstrained quadratic programming ⋮ New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ On the Approximability of the Minimum Weight $t$-partite Clique Problem ⋮ The table placement problem: a research challenge at the EWI 2007 ⋮ The sport teams grouping problem ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem ⋮ Disconnecting graphs by removing vertices: a polyhedral approach ⋮ Upper bounds and heuristics for the 2-club problem ⋮ Solving the maximum edge-weight clique problem in sparse graphs with compact formulations ⋮ Branch-and-price for \(p\)-cluster editing ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound ⋮ A new separation algorithm for the Boolean quadric and cut polytopes ⋮ Multilinear sets with two monomials and cardinality constraints

Cites Work

• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A cutting plane algorithm for a clustering problem
• An extended formulation approach to the edge-weighted maximal clique problem
• A cutting-plane approach to the edge-weighted maximal clique problem
• Min-cut clustering
• Cardinality constrained Boolean quadratic polytope
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
• Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
• A Lagrangian relaxation approach to the edge-weighted clique problem

This page was built for publication: New facets and a branch-and-cut algorithm for the weighted clique problem.