The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>

DOI10.1002/NET.21944MaRDI QIDQ6092622zbMATH OpenFDO

Authors Zacharie Ales, Arnaud Knippel

Publication date 23 November 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/NET.21944

zbMATH Keywords

branch-and-cutcombinatorial optimizationextended formulationgraph partitioninginteger programmingpolyhedral approach

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• \(b\)-tree facets for the simple graph partitioning polytope
• A cutting plane algorithm for a clustering problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• An Efficient Heuristic Procedure for Partitioning Graphs
• An extended edge-representative formulation for the \(K\)-partitioning problem
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• An Integer Programming Approach to Image Segmentation and Reconstruction Problems
• Clique-Web Facets for Multicut Polytopes
• Cluster analysis and mathematical programming
• Compact mathematical formulation for graph partitioning
• Facet-defining inequalities for the simple graph partitioning polytope
• Facets of the \(k\)-partition polytope
• Facets of the clique partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Graph partitioning using linear and semidefinite programming
• scientific article; zbMATH DE number 2159019 (Why is no real title available?)
• Linear and quadratic programming approaches for the general graph partitioning problem
• Min-cut clustering
• On Finding Dense Subgraphs
• On the asymmetric representatives formulation for the vertex coloring problem
• On the cut polytope
• On the solution of a graph partitioning problem under capacity constraints
• Orbitopal fixing
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Robust optimization of graph partitioning involving interval uncertainty
• Size-constrained graph partitioning polytopes
• Some simplified NP-complete graph problems
• The clique partitioning problem: Facets and patching facets
• The node capacitated graph partitioning problem: A computational study
• The partition problem
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(6)

• The \(k\)-partitioning problem
• An efficient heuristic for the \(k\)-partitioning problem
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• Mixed-integer linear programming formulations and column generation algorithms for the minimum normalized cuts problem on networks
• Optimizing warehouse product allocation at JD.com: a community detection-driven approach

This page was built for publication: The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>

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