Large-Scale Optimization Models with Applications in Biological and Emergency Response Networks
In this dissertation, we present new classes of network optimization models and algorithms, including heuristics and decomposition-based methods, to solve them. Overall, our applications highlight the breadth which optimization models can be applied and include problems in protein-protein interactio...
| Main Author: | |
|---|---|
| Format: | Text |
| Language: | unknown |
| Published: |
Clemson University Libraries
2021
|
| Subjects: | |
| Online Access: | https://tigerprints.clemson.edu/all_dissertations/2844 https://tigerprints.clemson.edu/cgi/viewcontent.cgi?article=3849&context=all_dissertations |
| Summary: | In this dissertation, we present new classes of network optimization models and algorithms, including heuristics and decomposition-based methods, to solve them. Overall, our applications highlight the breadth which optimization models can be applied and include problems in protein-protein interaction networks and emergency response networks. To our best knowledge, this is the first study to propose an exact solution approach for the star degree centrality (SDC) problem. In addition, we are the first who introduce the stochastic-pseudo star degree centrality problem and we are able to design a decomposition approach for this problem. For both problems, we introduce new complexity discussions where the practical difficulty of problems based on different graph types is classified. Moreover, we analyse an Arctic mass rescue event from an optimization perspective and create a novel network optimization model that examines the impact of the event on the evacuees and the time to evacuate them. We first consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the SDC problem, has been shown to be NP-complete. In this dissertation, we propose a new integer programming (IP) formulation, which has a fewer number of constraints and non-zero coefficients in them than the existing formulation in the literature. We present classes of networks where the problem is solvable in polynomial time and offer a new proof of NP-completeness that shows the problem remains NP-complete for both bipartite and split graphs. In addition, we propose a decomposition framework which is suitable for both the existing and the new formulations. We implement several acceleration techniques in this framework, motivated by those techniques used in Benders decomposition. We test our approaches on networks generated based on the Barabasi–Albert, Erdos–Renyi, and Watts–Strogatz models. Our decomposition approach outperforms solving the IP formulations in most of the ... |
|---|