Min-cut clustering

The authors describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. The authors discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.