A Benders Decomposition Approach to Correlation Clustering

Workshop:Machine Learning in HPC Environments

Authors: Jovita Lukasik and Margret Keuper (University of Mannheim) and Maneesh Singh and Julian Yarkony (Verisk Analytics, Inc)

Abstract: We tackle the problem of graph partitioning for image segmentation using correlation clustering (CC), which we treat as an integer linear program (ILP). We reformulate optimization in the ILP so as to admit efficient optimization via Benders decomposition, a classic technique from operations research. Our Benders decomposition formulation has many subproblems, each associated with a node in the CC instance's graph, which can be solved in parallel. Each Benders subproblem enforces the cycle inequalities corresponding to edges with negative (repulsive) weights attached to its corresponding node in the CC instance. We generate Magnanti-Wong Benders rows in addition to standard Benders rows to accelerate optimization. Our Benders decomposition approach provides a promising new avenue to accelerate optimization for CC, and, in contrast to previous cutting plane approaches, theoretically allows for massive parallelization.

Website:

Back to Machine Learning in HPC Environments Archive Listing

Back to Full Workshop Archive Listing