A cutting plane algorithm for globally solving low dimensional k-means clustering problems

2024-02-21 · Martin Ryner, Jan Kronqvist, Johan Karlsson

Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common such methods. There is a variety of approximate algorithms for the k-means problem, but computing the globally optimal solution is in general NP-hard. In this paper we consider the k-means problem for instances with low dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low dimensional structure and solve the problem to global optimality within reasonable time for large data sets with several clusters. The method builds on iteratively solving a small concave problem and a large linear programming problem. This gives a sequence of feasible solutions along with bounds which we show converges to zero optimality gap. The paper combines methods from global optimization theory to accelerate the procedure, and we provide numerical results on their performance.

📄 PDF Abstract BibTeX arXiv:2402.13595

Code (0)

등록된 구현이 없습니다.

Tasks

Clusteringglobal-optimization

Methods 이 논문이 사용한 방법론

k-Means Clustering k-Means Clustering is a clustering algorithm that divides a training set into $k$ different clusters of examples that are near each other. It works by initializing $k$…

Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization

2023-11-06 · Gabriele Dragotto, Stefan Clarke, Jaime Fernández Fisac, Bartolomeo Stellato

We consider the problem of solving a family of parametric mixed-integer linear optimization problems where some entries in the input data change. We introduce the concept of cutting-plane layer (CPL), i.e., a differentia…

Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

2022-04-15 · Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik

The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete opt…

BIG-bench Machine Learning

Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates

2023-07-17 · Kyle Mana, Fernando Acero, Stephen Mak, Parisa Zehtabi 외

Discrete optimization belongs to the set of $\mathcal{NP}$-hard problems, spanning fields such as mixed-integer programming and combinatorial optimization. A current standard approach to solving convex discrete optimizat…

Combinatorial Optimization Management reinforcement-learning Reinforcement Learning+1

Learning to Configure Separators in Branch-and-Cut

2023-11-08 · NeurIPS 2023 11

Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of c…

Management

Bayesian network learning with cutting planes

2012-02-14 · James Cussens

The problem of learning the structure of Bayesian networks from complete discrete data with a limit on parent set size is considered. Learning is cast explicitly as an optimisation problem where the goal is to find a BN …