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

Keisuke Sato, Yoichi Izunaga

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)236-245
Number of pages10
JournalComputers and Operations Research
Publication statusPublished - Jun 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs'. Together they form a unique fingerprint.

Cite this