Title: A branch-and-price approach with MILP formulation to modularity density maximization on graphs,
Abstract: For clustering of an undirected graph, this paper presents an exact algorithm
for the maximization of modularity density, a more complicated criterion to
overcome drawbacks of the well-known modularity. The problem can be interpreted
as the set-partitioning problem, which reminds us of its integer linear
programming (ILP) formulation. We provide a branch-and-price framework for
solving this ILP, or column generation combined with branch-and-bound. Above
all, 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 by a PC. Our solution method is
deterministic and the computation time is not affected by any stochastic
behavior. For one of them, 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.