| dc.description.abstract | In this thesis, the problem of maximizing algebraic connectivity is considered; an instantiation of this problem in the context of mechanical systems is as follows: We are given masses and a set E of springs with each spring having three attributes - (1) cost, (2) the pair of masses it can connect, and (3) stiffness. The problem is to build a structure within a specified budget B so that (a) it is connected, and (b) is as stiff as possible in the sense that the smallest non-zero natural frequency of the mechanical system is as high as possible. Algebraic connectivity in graph theory is an analog of the smallest non-zero natural frequency for such a connected, mechanical structure.
This problem may be thought of as a canonical problem in discrete system realization theory. It has several engineering applications in emerging areas such as control and localization of Un-manned Aerial Vehicles under resource constraints, air transportation systems, inference network design, among others. It is an NP-hard problem and, consequently, is non-trivial. This problem can be posed as a Mixed-Integer Semi-Definite Program (MISDP). Since it is a computationally difficult problem, developing formulations with tighter relaxations for the MISDP are useful as they can provide tight bounds, which in turn determine the computational time required by the Branch and Bound (B&B) solvers. For problem instances where it is difficult to determine the optimal solutions in a reasonable time, the upper bounds help establish posterior sub-optimality bounds for feasible solutions from heuristic methods. The primary novelty of this thesis is the refinement of prior MISDP formulation by adding constraints based on positive semi-definiteness of principal minors, and the subsequent relaxation of MISDP to find tighter upper bounds for the optimum.
The contributions of this thesis to the literature are as follows: (a) development of a relaxation of the MISDP based on2×2principal minors for upper bounding algebraic connectivity, (b)development of tighter upper bounds by implementing the iterative cutting plane algorithm on higher-order principal minors, and (c) development of a variant of the MISDP formulation based on the structure of optimal networks which results in a good feasible solution with better computational efficiency. | en |
