Abstract (EN)

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.