On the Solution of a Graph Partitioning Problem under Capacity Constraints

DOI10.1007/978-3-642-32147-4_26zbMath1370.90204OpenAlexW2124860471MaRDI QIDQ3167633

Pierre Bonami, Viet Hung Nguyen, Michel R. Klein, Michel Minoux

Publication date: 2 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32147-4_26

zbMATH Keywords

graph partitioningbranch-and-cutmixed integer quadratic programmingSONET ring

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (9)

Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Stochastic graph partitioning: quadratic versus SOCP formulations ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ A branch-and-cut algorithm for the connected max-\(k\)-cut problem ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Improved compact formulations for a wide class of graph partitioning problems in sparse graphs ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering

This page was built for publication: On the Solution of a Graph Partitioning Problem under Capacity Constraints