The node capacitated graph partitioning problem: A computational study

DOI10.1007/BF01581107MaRDI QIDQ1290618zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(49)

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

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)