Optimization Online


On globally solving the maximum weighted clique problem

Nam NGUYEN CANH(nam.nguyencanh***at***hust.edu.vn)

Abstract: 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].

Keywords: DC Programming, DCA, Quadratic Programming, Weighted Cliques, SemiDefinite Programming

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 11/30/2014
Entry Accepted: 12/01/2014
Entry Last Modified: 11/30/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society