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.

OPTIMISATION AND INTERDICTION PROBLEMS FOR NETWORK SAFETY

BOGGIO TOMASAZ, ALBERTO
2024

Abstract

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.
4-dic-2024
Inglese
CORDONE, ROBERTO
SASSI, ROBERTO
Università degli Studi di Milano
157
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R13472.pdf

accesso aperto

Dimensione 1.09 MB
Formato Adobe PDF
1.09 MB Adobe PDF Visualizza/Apri

I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14242/184241
Il codice NBN di questa tesi è URN:NBN:IT:UNIMI-184241