The node capacitated graph partitioning problem: A computational study

DOI10.1007/BF01581107zbMATH Open0919.90139OpenAlexW2090236751MaRDI QIDQ1290618FDOQ1290618

Authors: Carlos E. Ferreira, Alexander Martin, Cid Carvalho de Souza, Robert Weismantel, Laurence A. Wolsey 

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581107

Recommendations

• Formulations and valid inequalities of the node capacitated graph partitioning problem
• On the solution of a graph partitioning problem under capacity constraints
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts
• The partition problem

zbMATH Keywords

clusteringfinite element methodsgraph partitioningvalid inequalitiesbranch-and-cut algorithm\(k\)-partitioningequipartitioninglayout of electronic circuitsseparation heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• An Efficient Heuristic Procedure for Partitioning Graphs
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• On the cut polytope
• On the multiway cut polyhedron
• Title not available (Why is that?)
• A cutting plane algorithm for a clustering problem
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Min-cut clustering
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts
• Solving Multiple Knapsack Problems by Cutting Planes
• Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
• A branch-and-cut algorithm for the equicut problem
• On the magnetisation of the ground states in two dimensional Ising spin glasses
• A new approach to minimising the frontwidth in finite element calculations
• An algorithm for frontwidth reduction

Cited In (49)

• Facet-defining inequalities for the simple graph partitioning polytope
• A framework for solving mixed-integer semidefinite programs
• Engineering branch-and-cut algorithms for the equicut problem
• An overview of graph covering and partitioning
• Graph bisection revisited
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Reformulated acyclic partitioning for rail-rail containers transshipment
• On the polyhedral structure of uniform cut polytopes
• An exact combinatorial algorithm for minimum graph bisection
• Solving graph partitioning problems arising in tagless cache management
• From equipartition to uniform cut polytopes: extended polyhedral results
• Improved linearized models for graph partitioning problem under capacity constraints
• Tabu search and GRASP for the capacitated clustering problem
• An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Balanced partition of a graph for football team realignment in Ecuador
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Optimizing constrained subtrees of trees
• A reactive GRASP with path relinking for capacitated clustering
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• Large-scale pickup and delivery work area design
• Column-generation based bounds for the homogeneous areas problem
• Iterated maxima search for the maximally diverse grouping problem
• An extended edge-representative formulation for the \(K\)-partitioning problem
• Employee workload balancing by graph partitioning
• Combinatorial optimization of special graphs for nodal ordering and graph partitioning
• Orbitopal fixing
• Size-constrained graph partitioning polytopes
• Stochastic graph partitioning: quadratic versus SOCP formulations
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• A branch-and-bound algorithm for the acyclic partitioning problem
• Neighborhood decomposition-driven variable neighborhood search for capacitated clustering
• The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks
• An exact approach for the multi-constraint graph partitioning problem
• Title not available (Why is that?)
• An efficient semidefinite programming relaxation for the graph partition problem
• Cliques and clustering: A combinatorial approach
• On the solution of a graph partitioning problem under capacity constraints
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• A random-key GRASP for combinatorial optimization
• An exact algorithm for 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
• ILP-Based Local Search for Graph Partitioning
• The capacitated max \(k\)-cut problem
• A complementary column generation approach for the graph equipartition problem
• Finding optimal solutions to the graph partitioning problem with heuristic search
• Partitioning through projections: strong SDP bounds for large graph partition problems
• Political districting to minimize cut edges

This page was built for publication: The node capacitated graph partitioning problem: A computational study

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