Séminaire du GERAD: Branch-and-Price for the k-Club Partitioning and Covering Problems

Titre : Branch-and-Price for the k-Club Partitioning and Covering Problems

Conférencier : IRNICH, Stefan (Université Johannes Gutenberg de Mayence, Allemagne)

Résumé :
Relationships between objects can be modeled with graphs, where nodes represent the different objects and edges express the relationship. Social network analysis is an example where clusters, e.g., formed by members of a community, are studied using cliques and clique relaxations. A clique is a subgraph with pairwise directly connected nodes, i.e., a subgraph with diameter one. Several relaxations have been defined either in terms of distance (k-clique), degree (k-plex, k-core), diameter (k-club), or density. The majority of the literature deals with identifying such subgraphs of maximum cardinality or weight. In this presentation, we consider the problem of covering or partitioning a graph with a set of k-clubs. Note that a k-club is a subgraph with diameter at most k. For k=1, the clique partitioning problem results, which is equivalent to the graph coloring problem in the complement graph. For k>1, however, covering and partitioning are properly different problems because a subset of a k-club is not necessarily a k-club again. We present an exact solution approach to the k-club partitioning and covering problems based on branch-and-price. Herein, the subproblem consists of finding a k-club of maximum weight. We present heuristics and a new combinatorial branch-and-bound algorithm for its resolution. The most interesting part of the branch-and-price is the branching scheme. We derived branching rules that together guarantee integer solutions. Such branching rules are different and non-trivial for both cases, i.e., partitioning and covering, because a good rule should at the same time be compatible with the subproblem’s structure and solution approach, create a small number of branches, and generally improve the bound in all resulting problems.