A Column Generation Algorithm with Dynamic Constraint Aggregation for Minimum Sum-of-Squares Clustering

References

• Aloise D, Hansen P (2009) A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering. Pesqui. Oper. 29(3):503–516.Crossref, Google Scholar
• Aloise D, Hansen P (2011) Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering. J. Global Optim. 49(3):449–465.Crossref, Google Scholar
• Aloise D, Hansen P, Liberti L (2012) An improved column generation algorithm for minimum sum-of-squares clustering. Math. Programming 131:195–220.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115:351–385.Crossref, Google Scholar
• Bouarab H, El Hallaoui I, Metrane A, Soumis F (2017) Dynamic constraint and variable aggregation in column generation. Eur. J. Oper. Res. 262(3):835–850.Crossref, Google Scholar
• Brusco MJ (2006) A repetitive branch-and-bound procedure for minimum within-cluster sums of squares partitioning. Psychometrika 71(2):347–363.Crossref, Google Scholar
• Burgard JP, Moreira Costa C, Hojny C, Kleinert T, Schmidt M (2023) Mixed-integer programming techniques for the minimum sum-of-squares clustering problem. J. Global Optim. 87:133–189.Crossref, Google Scholar
• Desaulniers G, Lessard F, Saddoune M, Soumis F (2020) Dynamic constraint aggregation for solving very large-scale airline crew pairing problems. Desaulniers G, Soumis F, Lubbecke M, eds. SN Operations Research Forum, vol. 1 (Springer Nature, London), 1–23.Crossref, Google Scholar
• Diehr G (1985) Evaluation of a branch and bound algorithm for clustering. SIAM J. Sci. Statist. Comput. 6(2):268–284.Crossref, Google Scholar
• Du Merle O, Hansen P, Jaumard B, Mladenovic N (1999) An interior point algorithm for minimum sum-of-squares clustering. SIAM J. Sci. Comput. 21(4):1485–1505.Crossref, Google Scholar
• Elhallaoui I, Metrane A, Soumis F, Desaulniers G (2010) Multi-phase dynamic constraint aggregation for set partitioning type problems. Math. Programming 123:345–370.Crossref, Google Scholar
• Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53(4):632–645.Link, Google Scholar
• Forgy EW (1965) Cluster analysis of multivariate data: Efficiency versus interpretability of classifications. Biometrics 21(3):768–769. Google Scholar
• Hansen P, Mladenović N, Todosijević R, Hanafi S (2017) Variable neighborhood search: Basics and variants. EURO J. Comput. Optim. 5(3):423–454.Crossref, Google Scholar
• Koontz WLG, Narendra PM, Fukunaga K (1975) A branch and bound clustering algorithm. IEEE Trans. Comput. 100(9):908–915.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Mahajan M, Nimbhorkar P, Varadarajan K (2012) The planar k-means problem is np-hard. Theoret. Comput. Sci. 442:13–21.Crossref, Google Scholar
• Peng J, Wei Y (2007) Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1):186–205.Crossref, Google Scholar
• Peng J, Xia Y (2005) A new theoretical framework for k-means-type clustering. Chu W, Lin T, eds. Foundations and Advances in Data Mining (Springer, Berlin, Heidelberg, New York), 79–96.Crossref, Google Scholar
• Piccialli V, Sudoso AM, Wiegele A (2022) SOS-SDP: An exact solver for minimum sum-of-squares clustering. INFORMS J. Comput. 34(4):2144–2162.Link, Google Scholar
• Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• Rönnberg E, Larsson T (2019) An integer optimality condition for column generation on zero–One linear programs. Discrete Optim. 31:79–92.Crossref, Google Scholar
• Saddoune M, Desaulniers G, Elhallaoui I, Soumis F (2012) Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Sci. 46(1):39–55.Link, Google Scholar
• Sherali HD, Adams WP (2013) Reformulation–linearization techniques for discrete optimization problems. Pardalos PM, Du D-Z, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 2849–2896.Google Scholar
• Sherali HD, Desai J (2005) A global optimization RLT-based approach for solving the hard clustering problem. J. Global Optim. 32(2):281–306.Crossref, Google Scholar
• Sudoso AM, Aloise D (2025) A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering. https://doi.org/10.1287/ijoc.2024.0938.cd, https://github.com/INFORMSJoC/2024.0938.Google Scholar
• Venkateshan P (2020) A note on “the facility location problem with limited distances”. Transportation Sci. 54(6):1439–1445.Link, Google Scholar