Improved linearized models for graph partitioning problem under capacity constraints. (4th July 2017)

• Record Type: Journal Article
• Authors: Nguyen, Viet Hung; Minoux, Michel
• Is Part Of: Optimization methods and software. Volume 32:Number 4(2017)
• Page Start: 892
• Page End: 903
• Publication Date: 2017-07-04
• Subjects: graph partitioning -- capacity constraint -- 0/1 quadratically constrained programming -- linearization techniques -- branch-and-bound; 90C10 -- 90C57 -- 90C27 -- 90C11; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1230209
• Languages: English
• ISSNs: 1055-6788

Abstract

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.