Optimization Online


Parsimonious formulations for low-diameter clusters

Austin Buchanan (buchanan***at***okstate.edu)
Hosseinali Salemi (hosseinali.salemi***at***okstate.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.

Download: [PDF]

Entry Submitted: 09/11/2017
Entry Accepted: 09/11/2017
Entry Last Modified: 09/12/2017

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