A Binary Linear Programming-Based K-Means Approach for the Capacitated Centered Clustering Problem

Baumann, Philipp (16 December 2019). A Binary Linear Programming-Based K-Means Approach for the Capacitated Centered Clustering Problem. In: IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). Macau. 15.-18.12.2019.

Text A Binary Linear Programming-Based K-Means Approach for the Capacitated.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (153kB)

The k-means algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a variant of the kmeans algorithm that can account for complex side constraints. The key idea is to use binary linear programming for assigning objects to clusters. Unlike existing extensions of the k-means algorithm that are designed for accommodating specific types of constraints, our approach can be applied to a wide range of constrained clustering problems with minor modifications. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it to a state-of-the-art algorithm on a test set that comprises 18 instances of the capacitated centered clustering problem. The proposed approach performed particularly well on large-sized instances with more than 100 clusters. It even found new best-known solutions for the four largest instances in the test set.

Interest & Impact

Downloads

3 since deposited on 21 Jan 2020
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item