On the Maximum Flow Blocker Problem
Isma Bentoumi  1@  , Ali Ridha Mahjoub  2@  , Fabio Furini  3, 4@  , Sébastien Martin  5@  
1 : Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
Université Paris Dauphine-PSL, Centre National de la Recherche Scientifique : UMR7024
2 : Laboratoire dánalyse et modélisation de systèmes pour láide à la décision
Université Paris Dauphine-PSL
3 : Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  (LAMSADE)  -  Site web
CNRS : UMR7024, Université Paris IX - Paris Dauphine
Place de Lattre de Tassigny 75775 PARIS CEDEX 16 -  France
4 : Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”
5 : Huawei Technologies France [Boulogne-Billancour]
HUAWEI Technologies France

The Maximum Flow Blocker Problem (MFBP) is a bi-level optimization problem where the leader is a blocker problem and the follower is a Maximum Flow problem. The MFBP consists in determining a minimum weight subset of arcs, called interdicted arcs, to be removed from the graph such that the remaining maximum flow is no larger than a given threshold. The non-interdicted graph refers to the one induced by the set of arcs which are not interdicted. In telecommunication networks, a major issue consists in detecting and facing anomalies. In this context, the MFBP has a key role in resilience analysis, since it gives the maximum number of anomalies that can occur such that the network continue to be operational. To the best of our knowledge, the MFBP has not been addressed in the literature but a closely related problem, called the Maximum Flow Interdiction Problem (MFIP), has been largely studied. This problem consists in finding a set of interdicted arcs that respect a given budget and such that the maximum flow, remaining in the non-interdicted graph, is minimized. We prove that the two problems, MFBP and MFIP, are equivalent. In other words, one can transform an instance of the MFBP to one of the MFIP and vice versa. Using this relation, we develop a compact integer formulation for the MFBP and obtain some complexity results.


Personnes connectées : 2 Vie privée
Chargement...