The p-arborescence star problem: Formulations and exact solution approaches. (February 2019)

• Record Type: Journal Article
• Authors: Morais, Vinicius; Gendron, Bernard; Mateus, Geraldo Robson
• Is Part Of: Computers & operations research. Volume 102(2019)
• Page Start: 91
• Page End: 101
• Publication Date: 2019-02
• Subjects: Wireless sensor networks -- Arborescence -- Cutting-plane method; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.10.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We address an optimization problem arising in the design of ad-hoc wireless sensor networks. The so called p-arborescence star problem (P-ASP). We introduce MIP formulations and exact solution methods for P-ASP. Valid inequalities to strengthen the models are also given. We develop three branch-and-cut algorithms and a combinatorial Benders-based heuristic, which is used to provide the initial solution to exact algorithms. Optimal solutions obtained with the proposed branch-and-cut algorithms are reported for instances with at most 200 vertices and 60 cluster-heads. Abstract: We consider a problem arising in the design of ad-hoc wireless sensor networks. Given a connected bidirectional digraph with n sensors and a fixed sink, the p -arborescence star problem is the problem of clustering the sensors into p disjoint subsets and defining a directed backbone that spans the sink and all p cluster - heads, one for each cluster. The overall objective of the problem is to minimize the sum of intra and inter - cluster costs. We introduce and compare formulations based on directed cutset constraints and multicommodity flow variables. Valid inequalities to strengthen the models are also given. To solve these models, we develop efficient cutting-plane methods. We carry out extensive computational experiments and comparisons to illustrate the performance of our methods.