Integer programming formulations for distance-constrained network problems
Abstract
Network-based models (graphs) are among the most powerful tools for representing relationships and communications between different elements of a system in science, engineering, and business. In each of these scientific fields, nodes of a network represent distinct objects, and edges show relationships or similarities between them. Due to the ability of networks to model discrete objects in many different fields, network design and analysis have encountered an explosive growth during recent years. The presence of distance constraints in various network design and analysis problems such as detecting clusters and critical nodes, has been problematic and challenging for many researchers. These NP-hard combinatorial optimization problems are among the popular topics in network design and analysis and are challenging to be solved---especially when the number of nodes and/or edges of a network is large. Towards this end, we need to develop exact methods to identify low-diameter clusters and critical nodes of a network efficiently. In this dissertation, we introduce new integer programming formulations, algorithms, preprocessing techniques, and decomposition methods that allow us to find low-diameter clusters and critical nodes in relatively large networks.
Collections
- OSU Dissertations [11222]