1-s2.0-S1572528617300634-main
This journal article (Discrete Optimization, 2017) by Costa, Ng and Foo presents complete MILP reformulations for the modularity density maximization (MDM) clustering problem. It surveys linearization tools (McCormick/Fortet, dual reformulation, binary expansion, Charnes–Cooper-style fractional linearization), formulates auxiliary 0–1 NLPs (Aβ and Aα) that provide bounds needed for linearization, and derives four MILP variants for Aβ and two for Aα. The authors prove that the continuous relaxations of Aβ and Aα yield integer optimal solutions, and report computational experiments (several small network instances) showing MILP reformulations can be up to two orders of magnitude faster than solving the continuous NLP relaxations used previously.
Questions this document answers
18 April 2016
30 March 2017
24 April 2017