Integer Linear Programming Formulations for the Maximum Flow Blocker Problem

Given a directed graph with capacities and blocker costs associated with its arcs, we study the maximum flow blocker problem (MFBP) which asks to find a minimum-cost subset of arcs to be removed from the graph in such a way that the remaining maximum-flow value does not exceed a given threshold. The MFBP has applications in telecommunication networks and in the monitoring of civil infrastructures, among others. We propose two integer linear programming (ILP) formulations for the MFBP which are used to derive the first exact algorithms to optimally solve the problem. The first one, having an exponential number of constraints, is solved via a tailored branch-and-cut algorithm. The second one, having a polynomial number of variables and constraints, is solved via a state-of-the-art ILP solver. This formulation is obtained thanks to the main theoretical result of the paper that establishes a relationship between the MFBP and the maximum flow interdiction problem. The link is obtained by exploiting the specific structural properties of the two problems. The exact methods proposed in this paper are compared thanks to an extensive computational campaign on a set of real-world and synthetic instances. Our tests aim at evaluating the performance of the exact algorithms and at determining the features of the instances which can be solved to proven optimality