OPTIMISATION AND INTERDICTION PROBLEMS FOR NETWORK SAFETY

In this thesis, we explore optimisation problems related to security, focusing on real-world systems that can be modelled using graphs or binary matrices. The first problem we examine is the Weighted Safe Set Problem, a graph optimisation problem that seeks to identify vertex partitions satisfying specific dominance constraints between the parts. For this problem, we propose an exact combinatorial branch-and-bound algorithm alongside several randomised heuristics. Next, we introduce a family of Binary Interdiction Problems, referred to as Hard Interdiction Problems, involving two agents: the attacker, who acts as the leader, and the defender, who acts as the follower. The defender solves an optimisation problem after the attacker has interdicted the original instance by blocking certain elements, aiming to degrade the defender’s optimal solution as much as possible. For this family of problems, we improve upon state-of-the-art algorithmic frameworks by proposing new formulations and techniques. Finally, we define the concept of a Resilient Sample: a set of feasible defender solutions such that the attacker cannot simultaneously interdict all of them. We also present methods to compute Resilient Samples for several families of interdiction problems.