Formulations and valid inequalities of the node capacitated graph partitioning problem

DOI10.1007/BF02592198zbMath0855.90131OpenAlexW2046355282WikidataQ60395647 ScholiaQ60395647MaRDI QIDQ1814793

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

Publication date: 31 October 1996

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

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

zbMATH Keywords

clusteringknapsackequipartitionear decompositiondesign of electronic circuits and devicesfeasible multicutspartitioning the nodes of a graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

An overview of graph covering and partitioning, Iterated maxima search for the maximally diverse grouping problem, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, A branch-and-bound algorithm for the acyclic partitioning problem, Cluster analysis and mathematical programming, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Solving Graph Partitioning Problems Arising in Tagless Cache Management, The quadratic knapsack problem -- a survey, Size-constrained graph partitioning polytopes, On the polyhedral structure of uniform cut polytopes, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation, Orbitopal fixing, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, A polyhedral study of lifted multicuts, Cardinality constrained combinatorial optimization: complexity and polyhedra, Reformulated acyclic partitioning for rail-rail containers transshipment, Facet-defining inequalities for the simple graph partitioning polytope, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, Compact linearization for binary quadratic problems, Simple solution methods for separable mixed linear and quadratic knapsack problem, From equipartition to uniform cut polytopes: extended polyhedral results, Discrete relaxations of combinatorial programs, Lagrangian heuristics for the quadratic knapsack problem, Evaluating the quality of image matrices in blockmodeling, Cliques and clustering: A combinatorial approach, A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching, The node capacitated graph partitioning problem: A computational study, An approximate dynamic programming approach to convex quadratic knapsack problems, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Political districting to minimize cut edges, Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm

Cites Work

• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Facets of the clique partitioning polytope
• A cutting plane algorithm for a clustering problem
• The node capacitated graph partitioning problem: A computational study
• Min-cut clustering
• Some new classes of facets for the equicut polytope
• The partition problem
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Non-Separable and Planar Graphs
• On the cut polytope