More Like this

1. An MILP Approach for Distribution Grid Topology Identification using Inverter Probing

   https://doi.org/10.1109/PTC.2019.8810900  

   Taheri, Sina; Kekatos, Vassilis; Cavraro, Guido (June 2019, IEEE Power Tech Conference)

   Although knowing the feeder topology and line impedances is a prerequisite for solving any grid optimization task, utilities oftentimes have limited or outdated information on their electric network assets. Given the rampant integration of smart inverters, we have previously advocated perturbing their power injections to unveil the underlying grid topology using the induced voltage responses. Under an approximate grid model, the perturbed power injections and the collected voltage deviations obey a linear regression setup, where the unknown is the vector of line resistances. Building on this model, topology processing can be performed in two steps. Given a candidate radial topology, the line resistances can be estimated via a least-squares (LS) fit on the probing data. The topology attaining the best fit can be then selected. To avoid evaluating the exponentially many candidate topologies, this two-step approach is uniquely formulated as a mixed-integer linear program (MILP) using the McCormick relaxation. If the recovered topology is not radial, a second, computationally more demanding MILP confines the search only within radial topologies. Numerical tests explain how topology recovery depends on the noise level and probing duration, and demonstrate that the first simpler MILP yields a tree topology in 90% of the cases tested. 

   more » « less
2. Heuristic shortest hyperpaths in cell signaling hypergraphs

   https://doi.org/10.1186/s13015-022-00217-9  

   Krieger, Spencer; Kececioglu, John (December 2022, Algorithms for Molecular Biology)

   Abstract Background Cell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs , where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. The current state-of-the-art for shortest hyperpaths in cell signaling hypergraphs solves a mixed-integer linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees. Results We present, for the first time, a heuristic for general shortest hyperpaths that properly handles cycles , and is guaranteed to be efficient . We show the heuristic finds provably optimal hyperpaths for the class of singleton-tail hypergraphs, and also give a practical algorithm for tractably generating all source-sink hyperpaths. The accuracy of the heuristic is demonstrated through comprehensive experiments on all source-sink instances from the standard NCI-PID and Reactome pathway databases, which show it finds a hyperpath that matches the state-of-the-art mixed-integer linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the state-of-the-art, which finds no solution; on every such cyclic instance, enumerating all source-sink hyperpaths shows the solution found by the heuristic was in fact optimal . Conclusions The new shortest hyperpath heuristic is both fast and accurate . This makes finding source-sink hyperpaths, which in general may contain cycles, now practical for real cell signaling networks. Availability Source code for the hyperpath heuristic in a new tool we call  (as well as for hyperpath enumeration, and all dataset instances) is available free for non-commercial use at . 

   more » « less
3. Parallel Verification for delta-Equivalence of Neural Network Quantization

   https://doi.org/10.1007/978-3-031-65112-0_4  

   Huang, Pei; Yang, Yuting; Wu, Haoze; Daukantas, Ieva; Wu, Min; Jia, Fuqi; Barrett, Clark (January 2024, Springer Nature Switzerland)

   Avni, Guy; Giacobbe, Mirco; Johnson, Taylor T; Katz, Guy; Lukina, Anna; Narodytska, Nina; Schilling, Christian (Ed.)

   Quantization replaces floating point arithmetic with integer arithmetic in deep neural networks, enabling more efficient on-device inference with less power and memory. However, it also brings in loss of generalization and even potential errors to the models. In this work, we propose a parallelization technique for formally verifying the equivalence between quantized models and their original real-valued counterparts. In order to guarantee both soundness and completeness, mixed integer linear programming (MILP) is deployed as the baseline technique. Nevertheless, the incorporation of two networks as well as the mixture of integer and real number arithmetic make the problem much more challenging than verifying a single network, and thus using MILP alone is inadequate for the non-trivial cases. To tackle this, we design a distributed verification technique that can leverage hundreds of CPUs on high-performance computing clusters. We develop a two-tier parallel framework and propose property- and output-based partition strategies. Evaluated on perception networks quantized with PyTorch, our approach outperforms existing methods in successfully verifying many cases that are otherwise considered infeasible. 

   more » « less
4. A Convex Optimization Approach to Chance-Constrained Linear Stochastic Drift Counteraction Optimal Control

   https://doi.org/10.1109/CDC45484.2021.9683303  

   Tang, Sunbochen; Li, Nan; Kolmanovsky, Ilya; Zidek, Robert (December 2021, Proceedings of 2021 60th IEEE Conference on Decision and Control (CDC))

   In this paper, we propose a convex optimization approach to chance-constrained drift counteraction optimal control (DCOC) problems for linear systems with additive stochastic disturbances. Chance-constrained DCOC aims to compute an optimal control law to maximize the time duration before the probability of violating a prescribed set of constraints can no longer be maintained to be below a specified risk level. While conventional approaches to this problem involve solving a mixed-integer programming problem, we show that an optimal solution to the problem can also be found by solving a convex second-order cone programming problem without integer variables. We illustrate the application of chance-constrained DCOC to an automotive adaptive cruise control example. 

   more » « less
5. A Multilevel Spectral Framework for Scalable Vectorless Power/Thermal Integrity Verification

   https://doi.org/10.1145/3529534  

   Zhao, Zhiqiang; Feng, Zhuo (January 2023, ACM Transactions on Design Automation of Electronic Systems)

   Vectorless integrity verification is becoming increasingly critical to the robust design of nanoscale integrated circuits. This article introduces a general vectorless integrity verification framework that allows computing the worst-case voltage drops or temperature (gradient) distributions across the entire chip under a set of local and global workload (power density) constraints. To address the computational challenges introduced by the large power grids and three-dimensional mesh-structured thermal grids, we propose a novel spectral approach for highly scalable vectorless verification of large chip designs by leveraging a hierarchy of almost linear-sized spectral sparsifiers of input grids that can well retain effective resistances between nodes. As a result, the vectorless integrity verification solution obtained on coarse-level problems can effectively help compute the solution of the original problem. Our approach is based on emerging spectral graph theory and graph signal processing techniques, which consists of a graph topology sparsification and graph coarsening phase, an edge weight scaling phase, as well as a solution refinement procedure. Extensive experimental results show that the proposed vectorless verification framework can efficiently and accurately obtain worst-case scenarios in even very large designs. 

   more » « less