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.