Using mathematical programming to refine heuristic solutions for network clustering

Sonia Cafieri 1, 2 Pierre Hansen 3
1 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
2 IMT - Institut de Mathématiques de Toulouse UMR5219
3 HEC Montréal - HEC Montréal
Abstract : We propose mathematical programming based aproaches to refine graph clustering solutions computed by heuristics. Clustering partitions are refined by applying cluster splitting and a combination of merging and splitting actions. A refinement scheme based on iteratively fixing and releasing integer variables of a mixed-integer quadratic optimization formulation appears to be particularly efficient. Computational experiments show the effectiveness and efficiency of the proposed approaches.
Document type :
Book sections
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download
https://hal-enac.archives-ouvertes.fr/hal-01018034
Contributor : Céline Smith <>
Submitted on : Thursday, July 3, 2014 - 3:18:52 PM
Last modification on : Friday, January 10, 2020 - 9:08:59 PM
Long-term archiving on: Friday, October 3, 2014 - 11:30:01 AM

File

Cafieri_NET2013.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01018034, version 1

Collections

MAIAA | MAIAA-OPTIM | ENAC | CNRS | INSMI | IMT | UNIV-TLSE2 | TDS-MACS | OPTIM | UNIV-TLSE3 | UT1-CAPITOLE | RPAS

Citation

Sonia Cafieri, Pierre Hansen. Using mathematical programming to refine heuristic solutions for network clustering. P. Pardalos, M. Batsyn, V. Kalyagin. Models, Algorithms and Technologies for Networks Analysis Proceedings of the 3rd International Conference on Network Analysis, Springer, pp xxxx, 2014, Springer Proceedings in Mathematics & Statistics, 9783319097572. ⟨hal-01018034⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

504

Files downloads

259