Skip to main content
Thesis defences

PhD Oral Exam - Shabnam Mahmoudzadeh Vaziri, Industrial Engineering

Exact Algorithms for Network Fortification and Design Problems under Stochastic Interdiction


Date & time
Thursday, June 6, 2024
9 a.m. – 12 p.m.
Cost

This event is free

Organization

School of Graduate Studies

Contact

Nadeem Butt

Where

Engineering, Computer Science and Visual Arts Integrated Complex
1515 St. Catherine W.
Room 003.309

Wheel chair accessible

Yes

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

Networks such as telecommunication, supply chains, power distribution, transportation, and logistics play a vital role in sustaining social, economic, and industrial operations. However, networks are at risk of natural and man-made disruptions. With the increasing interconnectivity of networks, a disruption in one network can negatively affect other networks. Such disruptions can result in significant property damage, loss of human lives, and extensive interruptions in critical services. We use network interdiction models to analyze and reduce the effects of interdictions (disruptions) on the networks. Interdiction models represent a two-player sequential game between the interdictor, seeking to maximize damage, and the network operator, striving to optimize operations in the residual network. Network interdiction models identify the critical nodes and/or arcs of the network and can be extended to fortify the existing networks or design resilient networks. In this thesis, we study the design of distribution and multicommodity networks under stochastic interdictions. Furthermore, we focus on the fortification of spanning trees under stochastic interdictions.

The first paper investigates the distribution network design problem considering the effect of interdictions. Since interdiction outcomes can be uncertain in the real world, we consider the interdiction outcome as an uncertain parameter. We present a tri-level stochastic model for distribution network design considering the uncertain outcome of interdictions. We extend the model to consider the effects of correlated facility interdictions where interruptions at one facility affect the function of the nearby facilities. To solve the model, we present an exact solution approach based on the Benders decomposition algorithm. To improve the performance of the proposed Benders decomposition algorithm, we solve the stochastic subproblem using dual decomposition, and supervalid and valid inequalities are added to the master problem.

In the second paper, we focus on the design of a multicommodity network with interdictions. The designer does not have information about the interdiction resources; therefore, we consider the uncertainty in the number of interdictions by presenting a tri-level stochastic mathematical model. We present a branch-and-Benders-cut (BBC) algorithm to solve the model. To improve the efficiency of the BBC algorithm, we use acceleration techniques including warm start, variable fixing, cut selection, Pareto-optimal cuts, penalty reformulation, and supervalid and valid inequalities.

In the third paper, we study the fortification of minimum spanning tree (MST) and optimum communication spanning tree (OCST) problems under stochastic number of interdictions. The goal is to find the optimal fortification strategy in a way that the increase in the MST/OCST costs due to the interdiction of unfortified edges is minimized. We present a tri-level stochastic model to find the fortification strategy. In the first level, the defender determines the fortification strategy to minimize the expected maximum damage. In the second level, the interdictor interdicts the unfortified edges to maximize the MST/OCST cost. In the third level, the defender optimizes the MST/OCST cost after interdiction. We use backward sampling framework with waiting list acceleration technique to solve the deterministic and stochastic MST/OCST fortification problems.

Back to top

© Concordia University