Solving Chance-Constrained Spanning k-Core Problem via Decomposition and Integer Programming

Headnote

Abstract

Given a non-negative integer k, a graph of minimum degree at least k is called a k-core. The concept of k-cores can be used to design resilient networks that preserve low diameter and high vertex-connectivity upon limited vertex or edge failures. This article focuses on a chance-constrained version of the minimum spanning k-core problem under probabilistic edge failures. Specifically, given that the edges can fail randomly and independently, we want to find a subset of edges of minimum total cost such that the graph with this edge set is a k-core with probability at least 1 - α where α ∈ [0,1]. We first reformulate the non-convex chance-constrained optimization problem as a large-scale integer program. To solve it, we employ a decomposition and branch-and-cut framework recently introduced in the literature and discuss problem-specific enhancements of this approach. We report on our computational experiments designed to benchmark this decomposition branch-and-cut algorithm.

Keywords

Resilient network design, chance-constrained optimization, minimum spanning k-core, decomposition and branchand- cut

(ProQuest: ... denotes formulae omitted.)

1. Introduction

This paper investigates a new approach to the inter-hub network design problem [22] where a set of designated hubs need to be connected in a reliable manner to withstand and remain functional under limited/targeted hub or inter-hub link failures. Given a set of hubs represented by vertices in the network, the goal here is to specify which edges must be created to bestow the designed network with some desirable structural properties. The hubs could represent major airports in an airline network, or they could represent cluster-heads forming the virtual backbone of a wireless network [5].

The problem of interest can be broadly classified as a "resilient" network design problem, closely related to the well-known survivable network design problem studied by Steiglitz [31] and others [18] investigating telecommunication network design. In a survivable design, a specified number of redundant (edge or vertex) disjoint paths must exist between every pair of nodes, or between those in a designated set. This ensures that communication is not interrupted if a link or node fails destroying a communication path. Resilient network design requires not just redundant disjoint paths, but those with short lengths. The motivation comes from applications like wireless network design where 2-hop communication might be desirable...