An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs

For clustering of an undirected graph, this paper presents an exact algorithm for the maximization of modularity density, a more complicated criterion that overcomes drawbacks of the well-known modularity metric. The problem can be interpreted as the set-partitioning problem, a problem typically solved with an integer linear programming (ILP) formulation. We provide a branch-and-price framework for solving this ILP, i.e., column generation combined with branch-and-bound. Most importantly, we formulate the column generation subproblem to be solved repeatedly as a simpler mixed integer linear programming (MILP) problem. Acceleration techniques called the set-packing relaxation and the multiple-cutting-planes-at-a-time combined with the MILP formulation enable us to optimize the modularity density for famous test instances including ones with over 100 vertices in around four minutes on a PC. Our solution method is deterministic and the computation time is not affected by any stochastic behavior. For one of the instances, column generation at the root node of the branch-and-bound tree provides a fractional upper bound solution and our algorithm finds an integral optimal solution after branching.