Optimization Online


Complete mixed integer linear programming formulations for modularity density based clustering

Alberto Costa(costa***at***lix.polytechnique.fr)
Tsan Sheng Ng(isentsa***at***nus.edu.sg)
Lin Xuan Foo(foolinxuan***at***u.nus.edu)

Abstract: Modularity density maximization is a clustering method that improves some issues of the commonly-used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become computationally challenging when the size of the instances grows. In this paper we propose and compare some explicit MILP reformulations of these auxiliary binary NLPs, so that the modularity density maximization problem can be completely expressed as MILP. The resolution time is reduced by a factor up to two order of magnitude with respect to the one obtained with the binary NLPs.

Keywords: clustering; modularity density; mixed integer linear programming; reformulations

Category 1: Network Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 10/20/2016
Entry Accepted: 10/20/2016
Entry Last Modified: 10/20/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society