An improved column generation algorithm for minimum sum-of-squares clustering

DOI10.1007/S10107-010-0349-7zbMath1236.90095OpenAlexW2170006979MaRDI QIDQ662300

Pierre Hansen, Daniel Aloise, Leo Liberti

Publication date: 22 February 2012

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

Full work available at URL: https://doi.org/10.1007/s10107-010-0349-7

zbMATH Keywords

column generationclusteringsum-of-squaresACCPM

Mathematics Subject Classification ID

Clustering in the social and behavioral sciences (91C20) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Related Items (26)

Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections ⋮ Globally optimal clusterwise regression by column generation enhanced with heuristics, sequencing and ending subset optimization ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ K-medoids inverse regression ⋮ On strategies to fix degenerate \(k\)-means solutions ⋮ An exact algorithm for semi-supervised minimum sum-of-squares clustering ⋮ Location Problems with Cutoff ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Distance geometry and data science ⋮ On clustering and interpreting with rules by means of mathematical optimization ⋮ Semi-supervised \(k\)-means clustering via DC programming approach ⋮ Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering ⋮ Mixed-integer programming techniques for the minimum sum-of-squares clustering problem ⋮ Variable neighborhood search for harmonic means clustering ⋮ On the Weber facility location problem with limited distances and side constraints ⋮ Column generation bounds for numerical microaggregation ⋮ Constrained clustering by constraint programming ⋮ Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability ⋮ J-means and I-means for minimum sum-of-squares clustering on networks ⋮ A Computational Study of the DC Minimization Global Optimality Conditions Applied to K-Means Clustering ⋮ Optimization problems for machine learning: a survey ⋮ An exact algorithm for the two-mode \(KL\)-means partitioning problem ⋮ A memetic algorithm based on reformulation local search for minimum sum-of-squares clustering in networks ⋮ A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering ⋮ Variable neighborhood search for minimum sum-of-squares clustering on networks ⋮ K-means clustering via a nonconvex optimization approach

Uses Software

• Unnamed Item
• Unnamed Item
• UCI-ml
• Bonmin
• minlpBB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of global \(k\)-means, an incremental heuristic for minimum sum-of-squares clustering
• Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
• Solution of large-scale symmetric travelling salesman problems
• Improving dynamic programming strategies for partitioning
• Modified global \(k\)-means algorithm for minimum sum-of-squares clustering problems
• Design of hybrids for the minimum sum-of-squares clustering problem
• NP-hardness of Euclidean sum-of-squares clustering
• Variable neighbourhood search: Methods and applications
• Stabilized column generation
• Cluster analysis and mathematical programming
• Variable neighborhood search
• Heuristic methods for large centroid clustering problems
• The integration of an interior-point cutting plane method within a branch-and-price algorithm
• A repetitive branch-and-bound procedure for minimum within-cluster sums of squares partitioning
• A new efficient algorithm based on DC programming and DCA for clustering
• A scatter search approach for the minimum sum-of-squares clustering problem
• A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning
• Numerical methods for fuzzy clustering
• Mathematical classification and clustering
• A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems
• A global optimization RLT-based approach for solving the hard clustering problem
• The Cutting-Plane Method for Solving Convex Programs
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The Planar k-Means Problem is NP-Hard
• Reformulations in Mathematical Programming: Definitions and Systematics
• The Facility Location Problem with Limited Distances
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• TSPLIB—A Traveling Salesman Problem Library
• A Branch and Bound Clustering Algorithm
• Fuzzy Sets and Decisionmaking Approaches in Vowel and Speaker Recognition
• An Interior Point Algorithm for Minimum Sum-of-Squares Clustering
• Evaluation of a Branch and Bound Algorithm for Clustering
• On Nonlinear Fractional Programming
• A Dynamic Programming Algorithm for Cluster Analysis
• Variable neighborhood search: Principles and applications
• J-MEANS: A new local search heuristic for minimum sum of squares clustering

This page was built for publication: An improved column generation algorithm for minimum sum-of-squares clustering