Access the full text.
Sign up today, get an introductory month for just $19.
O. Merle, Daniel Villeneuve, J. Desrosiers, P. Hansen (1998)
Stabilized column generationDiscret. Math., 194
M. Inaba (1994)
Application of weighted Voronoi diagrams and randomization to variance-based k-clustering
H. Sherali, J. Desai (2005)
A Global Optimization RLT-based Approach for Solving the Hard Clustering ProblemJournal of Global Optimization, 32
(2008)
Methods and Applications
S. Elhedhli, J. Goffin (2004)
The integration of an interior-point cutting plane method within a branch-and-price algorithmMathematical Programming, 100
M. Padberg, G. Rinaldi (1991)
A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman ProblemsSIAM Rev., 33
R. Fisher (1936)
THE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMSAnnals of Human Genetics, 7
P. Hansen, B. Jaumard (2003)
Cluster Analysis and Mathematical Programming
I. Yeh (1998)
Modeling of strength of high-performance concrete using artificial neural networksCement and Concrete Research, 28
I. Stancu-Minasian (1997)
Nonlinear Fractional Programming
D.M. Ryan, B.A. Foster (1981)
Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling
B. Mirkin (2005)
Clustering for data mining - a data recovery approach
M. Brusco (2006)
A Repetitive Branch-and-Bound Procedure for Minimum Within-Cluster Sums of Squares PartitioningPsychometrika, 71
N. Mladenović, P. Hansen (1997)
Variable neighborhood searchComput. Oper. Res., 24
(1981)
An integer programming approach to scheduling
M. Grötschel, O. Holland (1991)
Solution of large-scale symmetric travelling salesman problemsMathematical Programming, 51
J. Kogan (2007)
Introduction to Clustering Large and High-Dimensional Data
(1964)
Concave programming under linear constraints
D. Steinley (2006)
K-means clustering: a half-century synthesis.The British journal of mathematical and statistical psychology, 59 Pt 1
É. Taillard (2003)
Heuristic Methods for Large Centroid Clustering ProblemsJournal of Heuristics, 9
(1991)
TSPLIB– a traveling salesman library
Z. Drezner, A. Mehrez, G. Wesolowsky (1991)
The Facility Location Problem with Limited DistancesTransp. Sci., 25
Daniel Aloise, P. Hansen (2008)
A branch-and-cut SDP-based algorithm for minimum sum-of-squares clusteringPesquisa Operacional, 29
(2007)
UCI machine learning repository
J. MacQueen (1967)
Some methods for classification and analysis of multivariate observations, 1
Daniel Aloise, P. Hansen (2008)
Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clusteringJournal of Global Optimization, 49
P. Hansen, B. Jaumard, Christophe Meyer (2000)
A Simple Enumerative Algorithm for Unconstrained 0-1 Quadratic Programming
P. Hansen, N. Mladenović (1998)
Variable neighborhood search: Principles and applicationsEur. J. Oper. Res., 130
J.E. Kelley (1960)
The cutting plane method for solving convex programsJ. SIAM, 8
B. Mirkin (1996)
Mathematical Classification and ClusteringJournal of the Operational Research Society, 48
(1977)
Fuzzy sets and decision making approaches in vowel and speaker recognition
R.A. Fisher (1936)
The use of multiple measurements in taxonomic problemsAnn. Eugen., VII
P. Hansen, E. Ngai, B. Cheung, N. Mladenović (2005)
Analysis of Global k-Means, an Incremental Heuristic for Minimum Sum-of-Squares ClusteringJournal of Classification, 22
P. Hansen, N. Mladenović (1999)
J-MEANS: a new local search heuristic for minimum sum of squares clusteringPattern Recognit., 34
(1999)
User manual for MINLP_BB
(1970)
Numerical method for fuzzy clustering
M. Mahajan, P. Nimbhorkar, K. Varadarajan (2009)
The planar k-means problem is NP-hardLect. Notes Comput. Sci., 5431
Michael Laszlo, Sumitra Mukherjee (2006)
A genetic algorithm using hyper-quadtrees for low-dimensional k-means clusteringIEEE Transactions on Pattern Analysis and Machine Intelligence, 28
(2005)
The use of the hyperbolic smoothing clustering method for planning the tasks of sanitary agents in combating dengue
J. Pacheco (2005)
A scatter search approach for the minimum sum-of-squares clustering problemComput. Oper. Res., 32
W. Koontz, P. Narendra, K. Fukunaga (1975)
A Branch and Bound Clustering AlgorithmIEEE Transactions on Computers, C-24
A. Bagirov (2008)
Modified global k-means algorithm for minimum sum-of-squares clustering problemsPattern Recognit., 41
H. Sherali, Warren Adams (1998)
Reformulation-Linearization Techniques for Discrete Optimization Problems
E. Forgy (1965)
Cluster analysis of multivariate data : efficiency versus interpretability of classificationsBiometrics, 21
Michael Laszlo, Sumitra Mukherjee (2007)
A genetic algorithm that exchanges neighboring centers for k-means clusteringPattern Recognit. Lett., 28
J. Ward (1963)
Hierarchical Grouping to Optimize an Objective FunctionJournal of the American Statistical Association, 58
B. Os, J. Meulman (2004)
Improving Dynamic Programming Strategies for PartitioningJournal of Classification, 21
(2007)
Exact method - based coordination of cluster ensembles . To appear in IEEETrans
R. Jensen (1969)
A Dynamic Programming Algorithm for Cluster AnalysisOper. Res., 17
M. Brusco, D. Steinley (2007)
A Comparison of Heuristic Procedures for Minimum Within-Cluster Sums of Squares PartitioningPsychometrika, 72
A. Likas, N. Vlassis, J. Verbeek (2003)
The global k-means clustering algorithmPattern Recognit., 36
(1956)
Sur la division des corps matèriels en parties
H.D. Sherali, W.P. Adams (1999)
Handbook of Combinatorial Optimization 1
M. Teboulle (2007)
A Unified Continuous Optimization Framework for Center-Based Clustering MethodsJ. Mach. Learn. Res., 8
Hoai Thi, M. Belghiti, T. Dinh (2007)
A new efficient algorithm based on DC programming and DCA for clusteringJournal of Global Optimization, 37
M. Mahajan, Prajakta Nimbhorkar, Kasturi Varadarajan (2009)
The planar k-means problem is NP-hardTheor. Comput. Sci., 442
Daniel Aloise, A. Deshpande, P. Hansen, P. Popat (2008)
NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 75
(2007)
BONMIN user’s manual
P. Merz (2003)
An iterated local search for minimum sum-of-squares clusteringLect. Notes Comput. Sci., 2810
E. Cureton, L. Cureton, R. Durfee (1970)
A METHOD OF CLUSTER ANALYSIS.Multivariate behavioral research, 5 1
J. Goffin, A. Haurie, J. Vial (1992)
Decomposition and nondifferentiable optimization with the projective algorithmManagement Science, 38
Leo Liberti (2009)
Reformulations in Mathematical Programming: Definitions and SystematicsRAIRO Oper. Res., 43
A.M. Bagirov, J. Yearwoord (2006)
Hierarchical grouping to optimize an objective functionEur. J. Oper. Res., 170
S. Vavasis (1991)
Nonlinear optimization: complexity issuesMathematics of Computation, 60
Grete Heinz, L. Peterson, Roger Johnson, C. Kerk (2003)
Exploring Relationships in Body DimensionsJournal of Statistics Education, 11
P. Hansen, N. Mladenović, J.A.M. Pérez (2008)
Variable neighborhood search: methods and applications4OR, 6
Yuzhen Ye (2021)
Clustering AlgorithmsWireless RF Energy Transfer in the Massive IoT Era
Yu Xia, Jiming Peng (2005)
A Cutting Algorithm for the Minimum Sum-of-Squared Error Clustering
Jiming Peng, Yu Xia (2004)
A new theoretical framework for K-means-type clustering
J. Pacheco, Olga Valencia (2003)
Design of hybrids for the minimum sum-of-squares clustering problemComput. Stat. Data Anal., 43
O. Merle, P. Hansen, B. Jaumard, N. Mladenović (1997)
An Interior Point Algorithm for Minimum Sum-of-Squares ClusteringSIAM J. Sci. Comput., 21
J. Kelley (1960)
The Cutting-Plane Method for Solving Convex ProgramsJournal of The Society for Industrial and Applied Mathematics, 8
G. Diehr (1985)
Evaluation of a Branch and Bound Algorithm for ClusteringSiam Journal on Scientific and Statistical Computing, 6
Anil Jain, M. Murty, P. Flynn (1999)
Data clustering: a reviewACM Comput. Surv., 31
R. Ling (1981)
Cluster analysis algorithms for data reduction and classification of objectsTechnometrics, 23
Given a set of entities associated with points in Euclidean space, minimum sum-of-squares clustering (MSSC) consists in partitioning this set into clusters such that the sum of squared distances from each point to the centroid of its cluster is minimized. A column generation algorithm for MSSC was given by du Merle et al. in SIAM Journal Scientific Computing 21:1485–1505. The bottleneck of that algorithm is the resolution of the auxiliary problem of finding a column with negative reduced cost. We propose a new way to solve this auxiliary problem based on geometric arguments. This greatly improves the efficiency of the whole algorithm and leads to exact solution of instances with over 2,300 entities, i.e., more than 10 times as much as previously done.
Mathematical Programming – Springer Journals
Published: Apr 20, 2010
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.