The clique partitioning problem: Facets and patching facets

DOI10.1002/NET.10004MaRDI QIDQ4537609zbMATH OpenOpenAlexFDO

Authors Maarten Oosten, Jeroen H. G. C. Rutten, Frits C. R. Spieksma

Publication date 1 July 2002

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.10004

zbMATH Keywords

polyhedral combinatoricsfacetsclique partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Facets of the clique partitioning polytope
• scientific article; zbMATH DE number 15357
• The partition problem
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• Facet-defining inequalities for the simple graph partitioning polytope

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1103047 (Why is no real title available?)
• scientific article; zbMATH DE number 863504 (Why is no real title available?)
• A Branch-and-Bound Approach Using Polyhedral Results for a Clustering Problem
• A cutting plane algorithm for a clustering problem
• Clique-Web Facets for Multicut Polytopes
• Faces for a linear inequality in 0–1 variables
• Facets of the clique partitioning polytope
• Fast Clustering Algorithms
• Grouping of parts and components in flexible manufacturing systems
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• On the partial order polytope of a digraph
• Problem Decomposition and Data Reorganization by a Clustering Technique
• The partition problem

Cited in

(49)

• Facet-defining inequalities for the simple graph partitioning polytope
• On Integrality in Semidefinite Programming for Discrete Optimization
• An overview of graph covering and partitioning
• Redundant constraints in the standard formulation for the clique partitioning problem
• Sequential-Merge Facets for Two-Dimensional Group Problems
• Disconnecting graphs by removing vertices: a polyhedral approach
• Transitive packing
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Reformulated acyclic partitioning for rail-rail containers transshipment
• The unconstrained binary quadratic programming problem: a survey
• New facets of the clique partitioning polytope
• scientific article; zbMATH DE number 1286488 (Why is no real title available?)
• A two-level graph partitioning problem arising in mobile wireless communications
• Exact algorithms for the minimum \(s\)-club partitioning problem
• Efficient enumeration of the optimal solutions to the correlation clustering problem
• Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• A three-phased local search approach for the clique partitioning problem
• Binary positive semidefinite matrices and associated integer polytopes
• The branch and cut method for the clique partitioning problem
• The biclique partitioning polytope
• Facets of the clique partitioning polytope
• Projection results for the \(k\)-partition problem
• An extended edge-representative formulation for the \(K\)-partitioning problem
• Concise integer linear programming formulation for clique partitioning problems
• Solving group technology problems via clique partitioning
• Fixed set search applied to the clique partitioning problem
• Lagrangian relaxation and pegging test for the clique partitioning problem
• Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem
• A cutting plane algorithm for a clustering problem
• Size-constrained graph partitioning polytopes
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• A branch-and-bound algorithm for the acyclic partitioning problem
• A polyhedral study of lifted multicuts
• A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
• Clique Partitioning for Clustering: A Comparison withK-Means and Latent Class Analysis
• Solving the clique partitioning problem as a maximally diverse grouping problem
• \(b\)-tree facets for the simple graph partitioning polytope
• Clique facets of the axial and planar assignment polytopes
• Clustering of microarray data via clique partitioning
• scientific article; zbMATH DE number 15357 (Why is no real title available?)
• Grouping products for the optimization of production processes: a case in the steel manufacturing industry
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• Chorded cycle facets of the clique partitioning polytope
• New bounds and constraint propagation techniques for the clique partitioning problem
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• \texttt{CP-Lib}: benchmark instances of the clique partitioning problem
• Political districting to minimize cut edges

This page was built for publication: The clique partitioning problem: Facets and patching facets

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