Efficient Network Reconfiguration by Randomized Switching

Abstract

We present an algorithm that efficiently computes nearly-optimal solutions to a class of combinatorial reconfiguration problems on weighted, undirected graphs. Inspired by societally relevant applications in networked infrastructure systems, these problems consist of simultaneously finding an unreweighted sparsified graph and nodal potentials that satisfy fixed demands, where the objective is to minimize some congestion criterion, e.g., a Laplacian quadratic form. These are mixed-integer nonlinear programming problems that are NP-hard in general. To circumvent these challenges, instead of solving for a single best configuration, the proposed randomized switching algorithm seeks to design a distribution of configurations that, when sampled, ensures that congestion concentrates around its optimum. We show that the proposed congestion metric is a generalized self-concordant function in the space of switching probabilities, which enables the use of efficient and simple conditional gradient methods. We implement our algorithm and show that it outperforms a state-of-the-art commercial mixed-integer second-order cone programming (MISOCP) solver by orders of magnitude over a large range of problem sizes.