Parsimonious formulations for low-diameter clusters
Austin Buchanan (buchananokstate.edu)
Abstract: In the analysis of networks, one often searches for tightly knit clusters. One property of a ``good'' cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or dominate several previously existing formulations. Our best-performing formulation uses only $n$ variables (quite unlike previous formulations) and imposes the diameter-at-most-$k$ constraints via an exponentially large class of cut-like inequalities. A relatively simple implementation of the cut-like formulation easily outperforms previous approaches, solving dozens of instances of the maximum $k$-club problem in a second or two that would take hours by other formulations. Moreover, the cut-like formulation is more general in the sense that it applies even when distances are not measured in terms of hops. While we consider only the $k$-club problem in this paper, the proposed techniques may also be useful in other applications where compact solutions are key (e.g., political districting and wildlife reserve design).
Keywords: $k$-club; low-diameter; cluster; integer programming; hop constraint; distance constraint; bounded diameter; length-bounded cut;
Category 1: Network Optimization
Category 2: Integer Programming
Category 3: Combinatorial Optimization
Citation: Submitted to a journal. Note: while the paper is under review, the C++ code is available upon request. Once the paper is accepted, the code will be made publicly available.
Entry Submitted: 09/11/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|