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.

[img] 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) | Request a copy

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.

Item Type:

Conference or Workshop Item (Paper)

Division/Institute:

03 Faculty of Business, Economics and Social Sciences > Department of Business Management > Institute of Financial Management > Professorship for Quantitative Methods in Business Administration

UniBE Contributor:

Baumann, Philipp

Subjects:

600 Technology > 650 Management & public relations

Series:

Proceedings of the 2019 IEEE International Conference on Industrial Engineering and Engineering Management

Language:

English

Submitter:

Juliana Kathrin Zurbrügg

Date Deposited:

21 Jan 2020 11:30

Last Modified:

21 Jan 2020 11:30

BORIS DOI:

10.7892/boris.138873

URI:

https://boris.unibe.ch/id/eprint/138873

Actions (login required)

Edit item Edit item
Provide Feedback