A Lagrangian relaxation approach to the edge-weighted clique problem (Q5937353)

From MaRDI portal
scientific article; zbMATH DE number 1618934
Language Label Description Also known as
English
A Lagrangian relaxation approach to the edge-weighted clique problem
scientific article; zbMATH DE number 1618934

    Statements

    A Lagrangian relaxation approach to the edge-weighted clique problem (English)
    0 references
    0 references
    0 references
    0 references
    2001
    0 references
    The authors consider the \(b\)-clique polytope which includes as special case the Boolean quadric polytope (as feasability set of the max cut problem) and which is itself a subset of the quadratic knapsack polyhedron. The polyhedral relations between the three types of polyhedra and new results on the \(b\)-clique polytope yield a large number of facet defining inequalities. These are combined with a Lagrangean relaxation to obtain very promissing numerical results for the edge-weighted clique problem.
    0 references
    0 references
    0 references
    0 references
    0 references
    linear programming
    0 references
    clique polytope
    0 references
    cut polytope
    0 references
    cutting plane
    0 references
    boolean quadric polytope
    0 references
    quadratic knapsack polytope
    0 references
    Lagrangian relaxation
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references