The node capacitated graph partitioning problem: A computational study

DOI10.1007/BF01581107zbMath0919.90139OpenAlexW2090236751MaRDI QIDQ1290618

Alexander Martin, Cid Carvalho De Souza, Carlos E. Ferreira, Laurence A. Wolsey, Robert Weismantel

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

branch-and-cut algorithmclusteringfinite element methodsgraph partitioningvalid inequalities\(k\)-partitioningequipartitioninglayout of electronic circuitsseparation heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment, An overview of graph covering and partitioning, Iterated maxima search for the maximally diverse grouping problem, 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-bound algorithm for the acyclic partitioning problem, Large-scale pickup and delivery work area design, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Graph bisection revisited, Solving Graph Partitioning Problems Arising in Tagless Cache Management, Optimizing constrained subtrees of trees, Size-constrained graph partitioning polytopes, Neighborhood decomposition-driven variable neighborhood search for capacitated clustering, Tabu search and GRASP for the capacitated clustering problem, ILP-Based Local Search for Graph Partitioning, On the polyhedral structure of uniform cut polytopes, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Orbitopal fixing, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Partitioning through projections: strong SDP bounds for large graph partition problems, An exact algorithm for graph partitioning, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, An exact approach for the multi-constraint graph partitioning problem, Employee workload balancing by graph partitioning, Reformulated acyclic partitioning for rail-rail containers transshipment, A framework for solving mixed-integer semidefinite programs, Facet-defining inequalities for the simple graph partitioning polytope, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, Improved compact formulations for a wide class of graph partitioning problems in sparse graphs, The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks, From equipartition to uniform cut polytopes: extended polyhedral results, A reactive GRASP with path relinking for capacitated clustering, Finding optimal solutions to the graph partitioning problem with heuristic search, An exact combinatorial algorithm for minimum graph bisection, Cliques and clustering: A combinatorial approach, Formulations and valid inequalities of the node capacitated graph partitioning problem, Balanced Partition of a Graph for Football Team Realignment in Ecuador, Unnamed Item, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Political districting to minimize cut edges, Column-generation based bounds for the homogeneous areas problem

Cites Work

• Unnamed Item
• A cutting plane algorithm for a clustering problem
• Min-cut clustering
• Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
• On the magnetisation of the ground states in two dimensional Ising spin glasses
• A branch-and-cut algorithm for the equicut problem
• 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
• A new approach to minimising the frontwidth in finite element calculations
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• On the multiway cut polyhedron
• An Efficient Heuristic Procedure for Partitioning Graphs
• On the cut polytope
• Solving Multiple Knapsack Problems by Cutting Planes
• An algorithm for frontwidth reduction