Improved linearized models for Graph Partitioning Problem under Capacity Constraints

Viet Hung Nguyen 1 Michel Minoux 1
1 DECISION
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We investigate a variant of the Graph Partitioning Problem with capacity constraints imposed on the clusters, giving rise to quadratic constraints in 0–1 formulations. Several compact linearized models of the problem are proposed and analysed: (a) a model featuring binary variables which results from the application of the standard Fortet linearization technique; (b) a more compact model featuring only binary variables, obtained by linearization after reformulation of the quadratic constraints as bilinear constraints; (c) a strengthened version of the latter model, still featuring variables. Computational experiments comparing the relative strength and efficiency of the various models on a series of test instances involving complete graphs with up to 50 nodes are reported and discussed.
Type de document :
Article dans une revue
Optimization, Methods and Software, Taylor and Francis, 2016, 〈10.1080/10556788.2016.1230209〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.sorbonne-universite.fr/hal-01369135
Contributeur : Viet Hung Nguyen <>
Soumis le : vendredi 30 juin 2017 - 12:26:18
Dernière modification le : mercredi 21 mars 2018 - 18:58:09
Document(s) archivé(s) le : lundi 22 janvier 2018 - 21:58:05

Fichier

Nguyen_2017_Improved_linearize...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Viet Hung Nguyen, Michel Minoux. Improved linearized models for Graph Partitioning Problem under Capacity Constraints. Optimization, Methods and Software, Taylor and Francis, 2016, 〈10.1080/10556788.2016.1230209〉. 〈hal-01369135〉

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

56