My Ph.D. dissertation is focused on developing new data-driven stochastic programming models, mathematical reformulations to linearize the original nonconvex models, and designing customized decomposition and approximation algorithms for solving optimization problems under endogenous (decision-dependent) uncertainty. Unlike traditional stochastic programs, where uncertainty is usually modeled using scenarios governed by a known probability distribution, in some application areas, such as retrofitting systems under imperfect and multi-level effects of protection resources on component reliability, it is beneficial to model the probability distributions of the uncertain parameters as a function of the decision variables. The stochastic program modeling this decision–dependent uncertainty is known as stochastic programming with endogenous uncertainty (SPEU). 

In a two-stage stochastic program (as shown in Figure 1), scenarios are generated to represent the realizations of uncertain parameters following a probability distribution, where each scenario represents a particular realization of the uncertain parameter. The optimization problem is decomposed into two-stage, where the first-stage decisions (x) are made without realizing the uncertainty. But the second-stage decisions (a.k.a., recourse decisions) are made after realizing the uncertainty, meaning the second-stage model is solved for each particular scenario after realizing the uncertainty. In optimization under endogenous uncertainty, decisions alter the probability distributions of uncertain parameters. For example, if a decision-maker invests more resources in a network component (e.g., better quality material) then the survival probability of that component will be higher when exposed to disruption, making the survival probability distribution to be a function of investment decision.   

In my Ph.D. dissertation, I developed a data-driven SPEU modeling framework where both exogenous and endogenous uncertainties coexist to model an integrated facility protection and transportation network design problem under random disruptions with the following realistic assumptions: (1) effect of protection resources is imperfect, (2) protection is multi-level, and (3) facilities have multiple post-disruption capacities. The proposed two-stage stochastic program integrates supervised machine learning models to estimate the conditional probability distributions of the facilities’ post-disruption capacities by analyzing historical data. To linearize the non-convex, nonlinear stochastic program, we developed a new mathematical reformulation technique. Utilizing the structure of the model, we developed a customized L-shaped decomposition algorithm to solve the problem as well as introduced several new valid inequalities to improve the computational efficiency of the algorithm. 

Figure 2: A distribution network subject to disruptions based on the southeastern United States 

Centralized government (land and fire management) agencies often face challenges in implementing wildfire prevention measures (hazardous fuel reduction treatments, such as prescribed burning, mechanical or chemical vegetation control) on nonindustrial private forest lands. These agencies can only incentivize the private landowners to encourage them to implement wildfire prevention measures on their lands through a cost-share program by sharing some portion of the implementation cost. The key challenges for the agencies in designing a cost-share program with their limited budget are: (1) the agency does not know whether a landowner will accept or reject the cost-share program for a given financial assistance amount, (2) different landowners’ land have different biophysical characteristics (e.g., vegetation density, moisture content, elevation, slope, etc.) and pose different amount of wildfire risk to the surrounding landscape. 

In my Ph.D. dissertation, I proposed a novel risk-based incentive structure design program to incentivize private landowners in implementing fuel reduction treatments on their lands, where (1) the landscape is divided into a number of raster cells (shown in Figure 3) based on the biophysical characteristics, and (2) different landowners are offered different incentive amounts by the budget-constrained government agency depending on the wildfire risks each landowner's land pose to the surrounding landscape. Another challenge the government agency faces is that the agency does not know whether a landowner will accept or reject the cost-share program for a given incentive amount. However, based on our landowner survey data, we found that the landowners are more likely to accept the cost-share program as the incentive amount increases, which makes the landowners' behavioral uncertainty endogenous to the incentive offer decision.  

We modeled the risk-based incentive structure design problem in reducing the risk of catastrophic future wildfires as a data-driven SPEU model. The proposed SPEU model accounts for the endogenous uncertainty in the landowners’ accept/reject decisions of the incentive. The proposed SPEU model utilizes a supervised machine learning model to estimate the landowners' likelihood of accepting the cost-share program by analyzing landowner survey data. Due to a large number of scenarios, the second-stage value of the two-stage SPEU model is computed using a simulation program that models the wildfire spread in the landscape accounting for the information on fuel reduction treatment, weather, and landscape characteristics. To model the wildfire spread as a network flow problem, the landscape is represented as a directed network (Figure 4), where each node represents a land parcel of the landscape and the arc weights represent the fire travel time between the land parcels. This work falls in the class of stochastic network interdiction problems, as the spatial optimization of fuel treatment resources prevents future catastrophic wildfires. 

Results based on real data from Santa Fe National Forest, New Mexico show that the proposed method can provide decision support to land management agencies for a realistic-sized landscape. This novel risk-based approach provides up to 37.3% more reduction in expected wildfire damage than the currently used methods. 

My foray into cyber-security research was through my M.S. research at Mississippi State University, (1)  cyber network security problems from the perspective of a cyber network owner (defender) who seeks to efficiently utilize the limited defense resources to deploy security countermeasures (e.g., firewalls, intrusion detection/prevention systems) to protect critical assets from cyber-attacks. In reality, cyber systems are vulnerable to multiple types of adversaries (attackers), each with different capabilities (e.g., skills, resources, etc.). Additionally, network owner faces uncertainty about the attackers’ capabilities, resources, and probabilities of attack success while making strategic decisions against them. In the presence of these uncertainties about attackers, it is crucial to find an optimal security countermeasures deployment decision that performs well under any particular attacker’s attributes (e.g., capabilities, resources, attack success probabilities).

To provide decision support to the cyber network owners, I used the concept of an attack graph that maps an organization’s cyber network topology to potential attack paths through which attackers can breach the critical assets of the organization. A node in the attack graph represents a security condition or an asset, whereas an arc represents an attacker’s action (attack). The goal of the network owners is to deploy countermeasures in the network that interdict (remove) the corresponding attack paths from the network, meaning that the attacker cannot use that path. Figure 5 demonstrates how attack graphs can be used to represent the potential attack paths for an example cyber system.

Figure 5: Attack graph representation of an example cyber system

In one of the works, I developed a two-stage stochastic mixed-integer programming model based on the attack graph concept to minimize the expected loss from cyber attacks by optimally deploying security countermeasures under uncertainty in attackers’ attack success probabilities [1]. We implemented a Sample Average Approximation (SAA) algorithm—a sampling strategy— and an L-shaped algorithm to solve the stochastic programming model for a large number of scenarios. 

In reality, the cyber network security against attackers can be viewed as a two-player Stackelberg game, where the network owner tries to minimize the loss, whereas the attacker seeks to maximize the loss to the defender. Therefore, to obtain a robust countermeasure deployment decision, the network owner needs to account for the attacker’s objective, making the problem a bi-level optimization. As the network owner has uncertainty about the attackers’ capabilities, some attackers having large capabilities (e.g., resources) can cause severe cyber-attacks, resulting in substantially large financial and reputation loss. Risk-neutral optimization models ignore the risk of these severe attacks. But, these severe cyber-attacks can cripple an organization. Because it is impossible to recover from such consequences in a short time; if recovery is possible at all. Therefore, it is crucial to account for the minimization of the risks of substantially large losses in the presence of uncertainty through a risk-averse modeling approach.

To provide decision-support to the risk-averse network managers, we developed a new risk-averse bi-level stochastic integer programming model that explicitly models (accounts for) multiple attackers with uncertainty in attackers’ capabilities and the risks of substantially large losses from severe attacks while computing the optimal decision [2]. In the stochastic programming model, we incorporated a risk-measure, conditional-value-at-risk (Figure 6), to model the risk of substantially large losses. We developed a customized constraint-and-column generation algorithm as well as several novel speed-up techniques in solving the risk-averse bi-level model. The proposed method provides optimal countermeasure deployment decisions that minimize the expected loss as well as the risk of substantially large losses from severe attacks. Results show that the stochastic risk-averse model provides substantially better network interdiction (countermeasure deployment) decisions (yielding up to 44.78% less expected loss from cyber-attacks)  than the existing models that ignore uncertainty in attackers’ capabilities and the risk of severe attacks.  

These countermeasure deployment decisions obtained from the optimization methods can then be mapped back in the cyber-network topology to determine on which network devices or links of an organization a security countermeasure should be deployed to protect critical assets. These methods can be easily adapted to secure different smart systems, such as smart manufacturing and smart power grids, from cyber-physical attacks.   

Figure 7: Effect of attackers' budget distribution on risk measure

Besides the mathematical optimization methods, I worked on developing/implementing supervised machine learning algorithms to detect malicious cyber nodes in large (millions of nodes graph), real-life, and highly class-imbalanced networks utilizing high-performance computing [3]. Malicious entities in the internet network, commonly known as bots, are a serious threat to internet network security, as these bots can perform a wide range of malicious activities such as sending spam emails, conducting distributed denial of service (DDoS), and click-fraud scams. It is challenging to detect bots in large, highly class-imbalanced network data, where the bot proportion is very small compared to the normal traffic. Most of the existing machine learning algorithms fail to detect bots (minority class) in highly class-imbalanced data, as the algorithms are biased towards the majority class. Moreover, most of the existing methods can only detect specific types of bots. Various types of bots can exist in a network, necessitating a generalized bot detection method capable of detecting various types of bots.

Therefore, we developed a novel bot detection method for large (millions of nodes), highly class-imbalanced (bot proportion is very low: 0.00583%), real data. We preprocessed the data to remove noisy observations. By analyzing the data, we developed and computed three novel features that can distinguish bots from normal traffic. Using these features, we developed the following supervised machine learning algorithms: Quadratic discriminant analysis, Gaussian Naïve Bayes, Support Vector Machine, K-Nearest Neighbor, and Random Forest. We trained these algorithms and tuned their parameters to reduce their bias towards the majority class. Due to large-scale (millions of node graphs) data, we used parallel computing to implement our methods in a high-performance computing environment. Results show that the proposed method substantially outperforms the existing methods in detecting bots from large, real-world, highly class-imbalanced data.

In another work, we developed a scalable distributed graph simulation algorithm using the concept of role mining, transition probability matrix, and parallel computing to generate very large-scale graphs (in the scale of billions of nodes) containing malicious nodes [4]. This distributed algorithm is capable of generating very large-scale graphs with accurate simulation of the behavior of malicious nodes from a given real-life input network. Figures 8, 9, and 10 demonstrate the original, simulated, and scaled-up simulated graphs, respectively. We also developed a hypergraph generation algorithm for a parallel computing environment to generate large hypergraphs [5].

I am studying the vulnerability of multi-hop wireless networks to jamming attacks. Gaining insights into network vulnerability is the first step in protecting wireless networks from adversaries. Unlike wired networks (e.g., transportation networks as shown in Figure 13), wireless networks (Figure 14) have a special property called radio interference that significantly affects the network throughput and makes the modeling of wireless networks to be different than wired networks. Due to this radio interference property, communications interfere with each other if they are within their range of interference and thus all communications cannot be active simultaneously, which substantially affects the network throughput. Figure 14 shows a connectivity graph of a small wireless communication network, where the same colored arcs can communicate (be active) simultaneously, which forms a schedulable set, a.k.a., independent set in graph theory. Based on this interference among communications, we can construct a conflict graph (or interference graph) to represent the radio interference. Figure 15 demonstrates a partial conflict graph corresponding to the connectivity graph shown in Figure 14. An independent set of nodes (equivalently a set of arcs in the connectivity graph) in the conflict graph can transmit data simultaneously, and scheduling maximal independent sets ensures maximum flow in the network.           

The rapid growth in e-commerce and demand for timely delivery of perishable or time-sensitive products have underscored the need for faster last mile delivery solutions. Aerial drones offer a distinct potential to improve the last mile delivery of time-sensitive products (e.g., pharmaceuticals, blood samples, and prepared food). However, despite having high speed and energy-efficiency, drones suffer from limited battery capacity and package weight carrying capacity that limit their operability in serving customers far from the distribution center (i.e., depot). Therefore, it is crucial to develop efficient solutions for drone deployment in last mile delivery of time-sensitive products, accounting for the power consumption and battery capacity of drones, requiring battery replacement to serve geographically distributed customers. 

In one of the works, we studied a deployment optimization problem for a homogeneous fleet of drones performing direct delivery to deliver packages with distinct release times and package pickup times from a depot to geographically distributed customers [1] as shown in Figure 1. The technological developments in drone industry, offer a wide variety of drone types with distinct characteristics—speed, power consumption, battery capacity, payload capacity, and cost. Therefore, we extended this research in our second work for efficient deployment of a mixed fleet of drones with different drone types (shown in Figure 2) for blood sample delivery [2]. We proposed efficient mixed-integer linear programming models, for routing and scheduling of drones with endogenous battery replacement decisions in an as-needed fashion to ensure safe and efficient operation of drones in serving geographically distributed customers. We also developed three solution approaches, including (1) solving the MILP model, enhanced with novel valid inequalities, with CPLEX; (2) a greedy heuristic algorithm; and (3) a heuristic Genetic algorithm. 

In one of the works, we studied a deployment optimization problem for a homogeneous fleet of drones performing direct delivery to deliver packages with distinct release times and package pickup times from a depot to geographically distributed customers [1] as shown in Figure 1. The technological developments in drone industry, offer a wide variety of drone types with distinct characteristics—speed, power consumption, battery capacity, payload capacity, and cost. Therefore, we extended this research in our second work for efficient deployment of a mixed fleet of drones with different drone types (shown in Figure 2) for blood sample delivery [2]. We proposed efficient mixed-integer linear programming models, for routing and scheduling of drones with endogenous battery replacement decisions in an as-needed fashion to ensure safe and efficient operation of drones in serving geographically distributed customers. 

We also developed three solution approaches, including (1) solving the MILP model, enhanced with novel valid inequalities, with CPLEX; (2) a greedy heuristic algorithm; and (3) a heuristic Genetic algorithm. 

We used actual drone flight test data conducted at the Idaho National Laboratory test site and performed a machine learning method to estimate the energy consumption of different types of drones during different flight segments (shown in Figure 3). Numerical results based on a real-life case study of prepared food delivery data from the San Francisco Bay Area, United States, and a real-life case study of actual blood sample delivery from Pendleton, United States, show that the Greedy algorithm solves the problem considerably faster (less than one seconds) than the other approaches, where CPLEX solver is unable to solve the problem within an hour. Results also demonstrate that the mixed fleet include drones with larger package weight carrying capacity and higher battery capacity as the package weight distribution includes heavier packages and drones need to detour through waypoints and fly over the road networks to avoid no-fly zones compared to flying in a straight path as shown in Figure 4.

Drones have limited delivery range and are limited to carry single package per trip, whereas ground vehicles (GVs) despite being less energy-efficient than drones, have long delivery range and are capable of carrying multiple packages in a single trip. Therefore, in our third study [3], we combined the strengths of drones and GVs and proposed an efficient mixed-integer linear programming model for an unsynchronized routing of a mixed fleet of drones and a homogeneous fleet of GVs to deliver packages with distinct package weights, package release times, and delivery due times to geographically distributed customers as shown in Figure 5.

To provide decision-support tools for logistics system owners, we developed an exact branch-and-cut (B&C) algorithm and a B&C integrated clustering-based heuristic algorithm to solve this problem. Results show that our exact B&C algorithm is up to 22 times faster than the Gurobi solver and our B&C-based heuristic solves the largest problem sizes efficiently while sacrificing the solution quality by a small amount. Results also demonstrate that using only drones in the fleet increases the cost by 141.4% compared to a mixed fleet of drones and GVs, whereas it reduces the energy consumption by 96%.  We also studied the effect of weather conditions (e.g., wind speed, precipitation, and temperature) on the operability of different drone types based on a one-year historical data of weather conditions of the San Francisco Bay Area as shown in Figure 6. Results show that the total cost and total energy consumption increase by 19.6% and 13.2%, respectively, as the weather changes from normal to adverse.

Using GVs to serve customers that are not directly reachable by drones limits the efficiency and autonomy of drones in the context of last mile delivery. Intermediate battery swapping machines (ABSMs) offer another viable alternative to extend the delivery range of drones by allowing frequent en-route battery swapping of drones to serve geographically distributed customers from a single distribution center (DC). Therefore, in our fourth study [4], we proposed a delivery network design that allows the mixed use of truck delivery and drone delivery supported by ABSMs to serve customers with uncertain demands as shown in Figure 7. We modeled each ABSM as a semi-open queuing network (shown in Figure 8) and adopted matrix geometric method (MGM) to evaluate the performance of ABSMs under different circumstances.

We developed three solution methods, including a heuristic Genetic algorithm, an exact cutting plane algorithm, and a step-wise linear approximation MILP model to solve the delivery network design problem. The numerical results demonstrate that solving the linearized MILP model with Gurobi results in 11.4 times faster runtime compared to the cutting-plane algorithm. Moreover, our proposed customized GA provides high-quality solutions and is 3.6 and 14.3 times faster than the linearized MILP model and the cutting-plane algorithm, respectively. Results also demonstrate that the cost-efficiency of different drone types varies across different demand rates as shown in Figure 9; using the shortest-range drones in the fleet is 39% more cost-efficient than the longest-range drones for the lowest demand rate whereas using the longest-range drones in the fleet is 61% more cost-efficient than the shortest-range drones for the highest demand rate. 

The increasing frequency and severity of natural disasters have led to widespread power outages, affecting public health and safety as shown in Figure 1. Therefore, rapid restoration of critical facilities around disasters is vital. However, traditional methods, such as network reconfiguration and dispatching repair crews are slow and labor-intensive. Moreover, the limited battery capacity of electric vehicles (EVs) and widely varying availability and readiness of personal EVs and electric buses (EBs) necessitates a faster and more reliable solution for restoring power to critical load, which are disconnected from the grid during a disaster. 

Our work is the first study to leverage efficient routing and energy scheduling of a heterogeneous fleet of electric school buses (ESBs) with their robust design, large battery capacity, and structured availability as government-owned assets for faster power restoration of critical isolated loads around disasters as shown in Figure 2. We addressed the following practical aspects: combined transportation and energy scheduling of ESBs, continuous tracking of the ESB’s state of charge (SOC), multiple back-and-forth trips of ESBs between isolated loads (referred to as "shelters") and charging stations (CSs), and route interdependency and spatial-wise coupling among multiple ESB routes. The goal of the decision-maker in this problem is to efficiently route and schedule the ESB fleet that minimizes the total cost including the total cost of the ESBs utilized, and the total transportation energy consumption cost while satisfying the total demand of all the shelters.

We formulated the proposed restoration problem as a novel efficient MILP model with routing and energy scheduling decisions of ESBs. To provide fast and accurate decision-support tools for emergency management agencies, we developed an efficient exact branch-and-price (B&P) algorithm and a customized heuristic B&P algorithm integrating dynamic programming and labeling algorithms.

The numerical results based on a realistic case study of Florida hospitals demonstrate that our proposed exact and heuristic B&P algorithms are 193 times and 343 times faster, respectively than the Gurobi solver. our proposed B&P-based solution algorithms better exploit the network sparsity feature (i.e., limited shelter-ESB type compatibility due to technology, infrastructure, or spatial limitations) than the Gurobi-based approach, enabling faster computations and handling larger problem instances across varying network sparsity levels.

Furthermore, the effective usable capacity metric indicates that the largest-capacity ESBs are 10 times more effective than the least-capacity ESBs. Results also demonstrate that weather severity significantly affects the required fleet size; the required fleet size increases by 429% as the weather changes from normal to adverse. Moreover, our findings show that as the inconvenience fee of demand shifting increases from no inconvenience fee ($0/kWh) to an extremely high inconvenience fee ($10,000/kWh), the percentage of shifted demand reduces to zero, whereas the total restoration cost and the required fleet size increases by up to 66% as shown in Figure 3.