  This paper focuses on the design of edge-weighted networks, whose robustness
is characterized by maximizing algebraic connectivity, or the smallest non-zero
eigenvalue of the Laplacian matrix. This problem is motivated by the
application of cooperative localization for accurately estimating positions of
autonomous vehicles by choosing a set of relative position measurements and
establishing associated communication links. 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. We solve this network design problem by formulating it as a
mixed-integer semi-definite program (MISDP) and reformulating it into a
mixed-integer linear program to obtain optimal solutions using cutting plane
algorithms. We propose a novel upper-bounding algorithm based on the hierarchy
of principal minor characterization of positive semi-definite matrices. We
further 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 find high-quality feasible solutions. We
show extensive computational results corroborating our proposed methods.

Systems and Control;Systems and Control;Optimization and Control