A cutting plane algorithm for a clustering problem

From MaRDI portal

Publication:1122492

Jump to:navigation, search

DOI10.1007/BF01589097zbMath0675.90072MaRDI QIDQ1122492

Martin Grötschel, Yoshiko Wakabayashi

Publication date: 1989

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

zbMATH Keywords

clustering polytope simplex method cutting plane implementation facets clique partitioning qualitative data analysis exact and heuristic separation routines

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)

Related Items

Medians for weight metrics in the covering graphs of semilattices, Combining clickstream analyses and graph-modeled data clustering for identifying common response processes, Flight gate assignment and recovery strategies with stochastic arrival and departure times, Multi-attribute community detection in international trade network, The partition problem, The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem, An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment, The clique partitioning problem: Facets and patching facets, A three-phased local search approach for the clique partitioning problem, A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming, An overview of graph covering and partitioning, Storage assignment and order batching problem in Kiva mobile fulfilment system, Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints, An extended edge-representative formulation for the \(K\)-partitioning problem, Concise integer linear programming formulation for clique partitioning problems, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, A branch-and-bound algorithm for the acyclic partitioning problem, A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks, Divisive heuristic for modularity density maximization, Cluster analysis and mathematical programming, Solving Graph Partitioning Problems Arising in Tagless Cache Management, On the partial order polytope of a digraph, Cluster Editing, Solving group technology problems via clique partitioning, Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint, Size-constrained graph partitioning polytopes, Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering, The affine hull of the schedule polytope for servicing identical requests by parallel devices, An efficient heuristic for the \(k\)-partitioning problem, A strong formulation for the graph partition problem, Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem, Improving heuristics for network modularity maximization using an exact algorithm, 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, Fixed set search applied to the clique partitioning problem, Exact Algorithms for Cluster Editing: Evaluation and Experiments, Optimal solutions for the double row layout problem, A randomized PTAS for the minimum consensus clustering with a fixed number of clusters, Efficient enumeration of the optimal solutions to the correlation clustering problem, The balanced maximally diverse grouping problem with integer attribute values, A polyhedral study of lifted multicuts, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, Detecting community structure: from parsimony to weighted parsimony, Comparison and polyhedral properties of valid inequalities for a polytope of schedules for servicing identical requests, Community detection with the weighted parsimony criterion, A New Composite Algorithm for Clustering Problems, New facets and a branch-and-cut algorithm for the weighted clique problem., New bounds and constraint propagation techniques for the clique partitioning problem, An exact approach for the multi-constraint graph partitioning problem, Additive approximation algorithms for modularity maximization, On the approximation of correlation clustering and consensus clustering, Efficient algorithms for divisive hierarchical clustering with the diameter criterion, Fitting semiparametric clustering models to dissimilarity data, Reformulated acyclic partitioning for rail-rail containers transshipment, Reformulation of a model for hierarchical divisive graph modularity maximization, Facet-defining inequalities for the simple graph partitioning polytope, Branch-and-cut approaches for \(p\)-cluster editing, A two-level graph partitioning problem arising in mobile wireless communications, Transitive packing, Improved compact formulations for a wide class of graph partitioning problems in sparse graphs, Projection results for the \(k\)-partition problem, A cutting plane algorithm for the windy postman problem, Clustering data that are graph connected, Exact algorithms for cluster editing: Evaluation and experiments, Consensus of partitions: a constructive approach, Lagrangian relaxation and pegging test for the clique partitioning problem, Redundant constraints in the standard formulation for the clique partitioning problem, Multiprocessor scheduling under precedence constraints: polyhedral results, Branch-and-price for \(p\)-cluster editing, Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping, The biclique partitioning polytope, Clique Partitioning for Clustering: A Comparison withK-Means and Latent Class Analysis, Efficient algorithms for cluster editing, Evaluating the quality of image matrices in blockmodeling, The Branch and Cut Method for the Clique Partitioning Problem, Cliques and clustering: A combinatorial approach, Facets of the clique partitioning polytope, Formulations and valid inequalities of the node capacitated graph partitioning problem, A branch-and-price procedure for clustering data that are graph connected, Toward Optimal Community Detection: From Trees to General Weighted Networks, Balanced Partition of a Graph for Football Team Realignment in Ecuador, Amalgamation of partitions from multiple segmentation bases: a comparison of non-model-based and model-based methods, Going weighted: parameterized algorithms for cluster editing, The node capacitated graph partitioning problem: A computational study, Exact algorithms for the minimum \(s\)-club partitioning problem, Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem, Going Weighted: Parameterized Algorithms for Cluster Editing, A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values, Clustering of microarray data via clique partitioning, A global optimization RLT-based approach for solving the hard clustering problem, Political districting to minimize cut edges, Models for machine-part grouping in cellular manufacturing, A cutting-plane approach to the edge-weighted maximal clique problem, Using Mathematical Programming to Refine Heuristic Solutions for Network Clustering, Experiments with a Non-convex Variance-Based Clustering Criterion, Min-cut clustering, Agrégation des similarités : une solution oubliée

Uses Software

LOLIB

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1122492&oldid=13168339"