New bounds and constraint propagation techniques for the clique partitioning problem
Publication date
2013-03-16
Document type
Forschungsartikel
Author
Pesch, Erwin
Organisational unit
Chair of Sustainable Operations and Logistics, University Augsburg
Scopus ID
Publisher
Elsevier
Series or journal
Discrete Applied Mathematics
ISSN
Periodical volume
161
Periodical issue
13-14
First page
2025
Last page
2037
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Branch and bound
Clique partitioning
Constraint propagation
Abstract
This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering. © 2013 Elsevier B.V. All rights reserved.
Version
Published version
Access right on openHSU
Metadata only access