On the solution of a graph partitioning problem under capacity constraints

DOI10.1007/978-3-642-32147-4_26MaRDI QIDQ3167633zbMATH OpenOpenAlexFDO

Authors 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

branch-and-cutgraph partitioningmixed integer quadratic programmingSONET ring

Mathematics Subject Classification ID

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

Recommendations

• Formulations and valid inequalities of the node capacitated graph partitioning problem
• scientific article; zbMATH DE number 3991298
• The node capacitated graph partitioning problem: A computational study
• Improved linearized models for graph partitioning problem under capacity constraints
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts

Cited in

(26)

• Cutting plane algorithms for solving a stochastic edge-partition problem
• The node capacitated graph partitioning problem: A computational study
• Multiset graph partitioning
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Integer programming formulations and efficient local search for relaxed correlation clustering
• Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
• An exact approach for the multi-constraint graph partitioning problem
• A graph theoretic approach to the slot allocation problem
• An efficient graph technique based dual-type algorithm for NMNF problems with large capacity constraints
• Solving graph partitioning problems arising in tagless cache management
• 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
• scientific article; zbMATH DE number 4076980 (Why is no real title available?)
• Improved linearized models for graph partitioning problem under capacity constraints
• Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem
• Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
• On the two-stage stochastic graph partitioning problem
• A branch-and-cut algorithm for the connected max-k-cut problem
• Size-constrained graph partitioning polytopes
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• Capacitated max-batching with interval graph compatibilities

This page was built for publication: On the solution of a graph partitioning problem under capacity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167633)