Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivity
This paper focuses on designing edge-weighted networks, whose robustness is characterized by maximizing algebraic connectivity, or the second smallest eigenvalue of the Laplacian matrix. This problem is motivated by cooperative vehicle localization, where accurately estimating relative position measurements and establishing communication links are essential. We also examine an associated problem where every robot is limited by payload, budget, and communication to pick no more than a specified number of relative position measurements. The basic underlying formulation for these problems is nonlinear and is known to be NP-hard. Our approach formulates this problem as a Mixed Integer Semi-Definite Program (MISDP), later reformulated into a Mixed Integer Linear Program (MILP) for obtaining optimal solutions using cutting plane algorithms. We introduce a novel upper-bounding algorithm based on principal minor characterization of positive semi-definite matrices and discuss a degree-constrained lower bounding formulation inspired by robust network structures. In addition, we propose a maximum cost heuristic with low computational complexity to identify high-quality feasible solutions for instances involving up to one hundred nodes. We show extensive computational results corroborating our proposed methods.
Code (1)
Tasks
Autonomous VehiclesPositionSimilar Papers 제목 키워드 기반
A Comparison of Strategies to Embed Physics-Informed Neural Networks in Nonlinear Model Predictive Control Formulations Solved via Direct Transcription
This study aims to benchmark candidate strategies for embedding neural network (NN) surrogates in nonlinear model predictive control (NMPC) formulations that are subject to systems described with partial differential equ…
Model Predictive ControlFormulations and scalability of neural network surrogates in nonlinear optimization problems
We compare full-space, reduced-space, and gray-box formulations for representing trained neural networks in nonlinear constrained optimization problems. We test these formulations on a transient stability-constrained, se…
GPUPractical and Performant Enhancements for Maximization of Algebraic Connectivity
Long-term state estimation over graphs remains challenging as current graph estimation methods scale poorly on large, long-term graphs. To address this, our work advances a current state-of-the-art graph sparsification a…
Revisiting the Optimal PMU Placement Problem in Multi-Machine Power Networks
To provide real-time visibility of physics-based states, phasor measurement units (PMUs) are deployed throughout power networks. PMU data enable real-time grid monitoring and control -- and are essential in transitioning…
Generalized Kalman Smoothing: Modeling and Algorithms
State-space smoothing has found many applications in science and engineering. Under linear and Gaussian assumptions, smoothed estimates can be obtained using efficient recursions, for example Rauch-Tung-Striebel and Mayn…
BIG-bench Machine LearningSurvey