An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs
From MaRDI portal
Publication:1734849
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.
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
Cites work
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- A Primer in Column Generation
- A cutting plane algorithm for modularity maximization problem
- A hybrid artificial immune network for detecting communities in complex networks
- Branch-and-price: Column generation for solving huge integer programs
- Complete mixed integer linear programming formulations for modularity density based clustering
- Divisive heuristic for modularity density maximization
- Efficient modularity density heuristics for large graphs
- Exact computational solution of modularity density maximization by effective column generation
- Implementing Mixed Integer Column Generation
- MILP formulations for the modularity density maximization problem
- On Nonlinear Fractional Programming
- Real-time freight locomotive rescheduling and uncovered train detection during disruption
- Selected Topics in Column Generation
- Stabilized column generation
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
Cited in
(9)- A branch-and-price procedure for clustering data that are graph connected
- A doubly nonnegative relaxation for modularity density maximization
- Divisive heuristic for modularity density maximization
- A study on modularity density maximization: column generation acceleration and computational complexity analysis
- Exact computational solution of modularity density maximization by effective column generation
- Modularity maximization to design contiguous policy zones for pandemic response
- MILP formulations for the modularity density maximization problem
- Modified modularity density maximization and density ratio heuristic
- Complete mixed integer linear programming formulations for modularity density based clustering
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)
