@book{8b47f70741ae4e10ba2ae191cc696b1d,

title = "A Lagrangian relaxation approach to the edge-weighted clique problem",

abstract = "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.",

keywords = "EWI-3296, MSC-90C27, METIS-141301, IR-65665, MSC-90D12",

author = "M.M.G. Hunting and U. Faigle and Walter Kern",

note = "Imported from MEMORANDA",

year = "1998",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum / Faculty of Mathematical Sciences",

publisher = "Universiteit Twente",

number = "1476",

}