The $b$-clique polytope $CP^n_b$ is the convex hull of the node and edge incidence vectors of all subcliques of size at most $b$ of a complete graph on $n$ nodes. Including the Boolean quadric polytope $QP^n$ as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over $QP^n_n$. The problem of optimizing linear functions over $CP^n_b$ has so far been approached via heuristic combinatorial algorithms and cutting-plane methods. We study the structure of $CP^n_b$ in further detail and present a new computational approach to the linear optimization problem based on Lucena's suggestion of integrating cutting planes into a Lagrangian relaxation of an integer programming problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.
|Place of Publication||Enschede|
|Number of pages||21|
|Publication status||Published - 1998|
|Name||Memorandum / Faculty of Mathematical Sciences|
|Publisher||Department of Applied Mathematics, University of Twente|
Hunting, M. M. G., Faigle, U., & Kern, W. (1998). A Lagrangian relaxation approach to the edge-weighted clique problem. (Memorandum / Faculty of Mathematical Sciences; No. 1476). Enschede: Universiteit Twente.