Date of Award
August 2021
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Industrial Engineering
Committee Member
Thomas C Sharkey
Committee Member
Chrysafis Vogiatzis
Committee Member
Yongjia Song
Committee Member
Emily Tucker
Abstract
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 instances in terms of both solution time and solution quality; this is especially true when the graph gets larger and denser. We then test the decomposition algorithm on large-scale protein-protein interaction networks, for which SDC was shown to be an important centrality metric.
We then introduce the stochastic pseudo-star degree centrality problem and propose methods to solve it exactly. The goal is to identify an induced pseudo-star, which is defined as a collection of nodes which form a star network with a certain probability, such that it maximizes the sum of the probability values in the unique assignments between the star and its open neighborhood. In this problem, we are specifically interested in a feasible pseudo-star, where the feasibility is measured as the product of the existence probabilities of edges between the center node and leaf nodes and the product of one minus the existence probabilities of edges among the leaf nodes. We then show that the problem is NP-complete on general graphs, trees, and windmill graphs. We initially propose a non-linear binary optimization model to solve this problem. Subsequently, we linearize our model via McCormick inequalities and develop a branch-and-Benders-cut framework to solve it. We generate Logic-Based-Benders cuts as alternative feasibility cuts and examine several acceleration techniques. The performance of our implementation is tested on randomly generated networks based on small-world (SW) graphs. The SW networks resemble large-scale protein-protein interaction networks for which the deterministic star degree centrality has been shown to be an efficient group-based centrality metric in order to detect essential proteins. Our computational results indicate that the Benders implementation outperforms solving the model directly via a commercial solver in terms of both the solution time and the solution quality in the majority of the test instances.
Lastly, we turn our attention to a network optimization problem with an application in Arctic emergency response. We study a model that optimizes the response to a mass rescue event in Arctic Alaska. The model contains dynamic logistics decisions for a large-scale maritime evacuation with the objectives of minimizing the impact of the event on the evacuees and the average evacuation time. Our proposed optimization model considers two interacting networks - the network that moves evacuees from the location of the event to out of the Arctic (e.g., a large city in Alaska such as Anchorage) and the logistics network that moves relief materials to evacuees during the operations. We model the concept of deprivation costs by incorporating priority levels capturing the severeness of evacuees' current medical situation and period indicating the amount of time an evacuee has not received key relief resources. Our model is capable of understanding the best possible response given the current locations of response resources and is used to assess the effectiveness of an intuitive heuristic that mimics emergency response decision-making.
Recommended Citation
Camur, Mustafa Can, "Large-Scale Optimization Models with Applications in Biological and Emergency Response Networks" (2021). All Dissertations. 2844.
https://open.clemson.edu/all_dissertations/2844