More Like this

1. Algorithms for tensor network contraction ordering

   https://doi.org/10.1088/2632-2153/ab94c5  

   Schindler, Frank ; Jermyn, Adam S. ( July 2020 , Machine Learning: Science and Technology)

   Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance.

    

   more » « less
2. Computing Volumes of Adjacency Polytopes via Draconian Sequences

   https://doi.org/10.37236/9768  

   Davis, Robert ; Chen, Tianran ( January 2022 , The Electronic Journal of Combinatorics)

   Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The ``"PQ-type" adjacency polytope, denoted $\nabla^{\mathrm{PQ}}_G$ and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for $\nabla^{\mathrm{PQ}}_G$ can be rephrased as counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $1$ and, for $2$-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $\nabla^{\mathrm{PQ}}_G$ when $G$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs $G$ which are planar but not outerplanar that are worth additional study. 

   more » « less
3. Dynamic reliability of infrastructure networks using augmented Monte Carlo simulation

   Zhou, X. ; Duenas-Osorio, L. ( September 2022 , The 13th International Conference on Structural Safety and Reliability (ICOSSAR 2021-2022))

   Li, J. ; Spanos, P. D. ; Chen, J. B. ; Peng, Y. B. (Ed.)

   Infrastructure networks offer critical services to modern society. They dynamically interact with the environment, operators, and users. Infrastructure networks are unique engineered systems, large in scale and high in complexity. One fundamental issue for their reliability assessment is the uncertainty propagation from stochastic disturbances across interconnected components. Monte Carlo simulation (MCS) remains approachable to quantify stochastic dynamics from components to systems. Its application depends on time efficiency along with the capability of delivering reliable approximations. In this paper, we introduce Quasi Monte Carlo (QMC) sampling techniques to improve modeling efficiency. Also, we suggest a principled Monte Carlo (PMC) method that equips the crude MCS with Probably Approximately Correct (PAC) approaches to deliver guaranteed approximations. We compare our proposed schemes with a competitive approach for stochastic dynamic analysis, namely the Probability Density Evolution Method (PDEM). Our computational experiments are on ideal but complex enough source-terminal (S-T) dynamic network reliability problems. We endow network links with oscillators so that they can jump across safe and failed states allowing us to treat the problem from a stochastic process perspective. We find that QMC alone can yield practical accuracy, and PMC with a PAC algorithm can deliver accuracy guarantees. Also, QMC is more versatile and efficient than the PDEM for network reliability assessment. The QMC and PMC methods provide advanced uncertainty propagation techniques to support decision makers with their reliability problems. 

   more » « less
4. Applying Machine Learning Methods to Improve All-Terminal Network Reliability

   https://doi.org/10.1109/RAMS51473.2023.10088254  

   Azucena, José ; Hashemian, Farid ; Liao, Haitao ; Pohl, Edward ( January 2023 , 2023 Annual Reliability and Maintainability Symposium (RAMS))

   One essential task in practice is to quantify and improve the reliability of an infrastructure network in terms of the connectivity of network components (i.e., all-terminal reliability). However, as the number of edges and nodes in the network increases, computing the all-terminal network reliability using exact algorithms becomes prohibitive. This is extremely burdensome in network designs requiring repeated computations. In this paper, we propose a novel machine learning-based framework for evaluating and improving all-terminal network reliability using Deep Neural Networks (DNNs) and Deep Reinforcement Learning (DRL). With the help of DNNs and Stochastic Variational Inference (SVI), we can effectively compute the all-terminal reliability for different network configurations in DRL. Furthermore, the Bayesian nature of the proposed SVI+DNN model allows for quantifying the estimation uncertainty while enforcing regularization and reducing overfitting. Our numerical experiment and case study show that the proposed framework provides an effective tool for infrastructure network reliability improvement. 

   more » « less
5. Node-weighted Network Design in Planar and Minor-closed Families of Graphs

   https://doi.org/10.1145/3447959  

   Chekuri, Chandra ; Ene, Alina ; Vakilian, Ali ( June 2021 , ACM Transactions on Algorithms)

   null (Ed.)

   We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max  uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log  n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm. 

   more » « less