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.

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2024

Author dc:creator

• BOGGIO TOMASAZ, ALBERTO

Contributors dc:contributor

• supervisore: R. Cordone ; co-supervisore: G. Righini ; coordinator: R. Sassi
• A. BOGGIO TOMASAZ
• CORDONE, ROBERTO
• SASSI, ROBERTO

• Weighted Safe Set Problem
• Branch and Bound
• GRASP
• Delayed Termination
• Scatter Search
• Binary Interdiction Problem
• Shortest Path Interdiction Problem
• Set Covering Interdiction Problem
• Restricted Response Relaxation
• Single Level Reformulation
• Generalised Covering Decomposition
• Diversification
• Resilient Samples
• Settore INFO-01/A - Informatica
• Settore MATH-06/A - Ricerca operativa

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

http://dx.doi.org/10.13130/boggio-tomasaz-alberto_phd2024-12-04
10.13130/boggio-tomasaz-alberto_phd2024-12-04

OAI identifier oai:identifier

oai:air.unimi.it:2434/1119489