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

DOI10.1016/J.COR.2018.01.012zbMATH Open1458.90625arXiv1705.02961OpenAlexW2802839594WikidataQ129914958 ScholiaQ129914958MaRDI QIDQ1734849FDOQ1734849

Authors: Keisuke Sato, Yoichi Izunaga 

Publication date: 27 March 2019

Published in: Computers \& Operations Research (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1705.02961

Recommendations

• MILP formulations for the modularity density maximization problem
• Complete mixed integer linear programming formulations for modularity density based clustering
• Exact computational solution of modularity density maximization by effective column generation
• Divisive heuristic for modularity density maximization
• A cutting plane algorithm for modularity maximization problem

zbMATH Keywords

graph clusteringbranch-and-priceset partitioningmodularity densitymultiple cutting planesset-packing relaxation

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Mixed integer programming (90C11)

Cites Work

• On Nonlinear Fractional Programming
• Selected Topics in Column Generation
• Stabilized column generation
• Branch-and-price: Column generation for solving huge integer programs
• Title not available (Why is that?)
• A Primer in Column Generation
• Implementing Mixed Integer Column Generation
• MILP formulations for the modularity density maximization problem
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Divisive heuristic for modularity density maximization
• Efficient modularity density heuristics for large graphs
• Real-time freight locomotive rescheduling and uncovered train detection during disruption
• Exact computational solution of modularity density maximization by effective column generation
• A hybrid artificial immune network for detecting communities in complex networks
• Complete mixed integer linear programming formulations for modularity density based clustering
• A cutting plane algorithm for modularity maximization problem

Cited In (9)

• Complete mixed integer linear programming formulations for modularity density based clustering
• A doubly nonnegative relaxation for modularity density maximization
• MILP formulations for the modularity density maximization problem
• Exact computational solution of modularity density maximization by effective column generation
• Modified modularity density maximization and density ratio heuristic
• Divisive heuristic for modularity density maximization
• Modularity maximization to design contiguous policy zones for pandemic response
• A branch-and-price procedure for clustering data that are graph connected
• A study on modularity density maximization: column generation acceleration and computational complexity analysis

Uses Software

• Gurobi

This page was built for publication: An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1734849)