A binary linear programming-based k-means algorithm for clustering with must-link and cannot-link constraints

Baumann, Philipp (2020). A binary linear programming-based k-means algorithm for clustering with must-link and cannot-link constraints. In: 2020 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (pp. 324-328). IEEE 10.1109/IEEM45057.2020.9309775

[img] Text
A_Binary_Linear_Programming-Based_K-Means_Algorithm_For_Clustering_with_Must-Link_and_Cannot-Link_Constraints.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (4MB) | Request a copy

Clustering is probably the most extensively studied problem in unsupervised learning. Traditional clustering algorithms assign objects to clusters exclusively based on features of the objects. Constrained clustering is a generalization of traditional clustering where additional information about a dataset is given in the form of constraints. It has been shown that the clustering accuracy can be improved substantially by accounting for these constraints. We consider the constrained clustering problem where additional information is given in the form of must-link and cannot-link constraints for some pairs of objects. Various algorithms have been developed for this specific clustering problem. We propose a binary linear programming-based k-means approach that can consider must-link and cannot-link constraints. In a computational experiment, we compare the proposed algorithm to the DILS CC algorithm, which represents the state-of-the-art. Our results on 75 problem instances indicate that the proposed algorithm delivers better clusterings than the DILS CC algorithm in much shorter running time.

Item Type:

Conference or Workshop Item (Paper)


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


600 Technology > 650 Management & public relations






Nina Ackermann

Date Deposited:

23 Jul 2021 10:28

Last Modified:

23 Jul 2021 10:28

Publisher DOI:






Actions (login required)

Edit item Edit item
Provide Feedback