On globally solving the maximum weighted clique problem

In this paper, we consider a combinatorial optimization problem, the Maximum Weighted Clique Problem (MWCP), a NP-hard problem. The considered problem is first formulated in the form of binary constrained quadratic program and then reformulated as a Difference Convex (DC) program. A global optimal solution is found by applying DC Algorithm (DCA) in combining with Branch and Bound scheme with SDP relaxation technique. Computational experiments are reported for problem instances provided by Macambria and de Souza [4] and other instances generated following the scheme of H.Spath [24].

Article

Download

View On globally solving the maximum weighted clique problem