.png){kind=icon}
.png){kind=icon}
Return
Integer linear programming formulations for the maximum flow blocker problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2025.02.013.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a network with capacities and blocker costs associated with its arcs, we study the maximum flow blocker problem (FB). This problem seeks to identify a minimum-cost subset of arcs to be removed from the network, ensuring that the maximum flow value from the source to the destination in the remaining network does not exceed a specified threshold. The FB finds applications in telecommunication networks and monitoring of civil infrastructures, among other domains. We undertake a comprehensive study of several new integer linear programming (ILP) formulations designed for the FB. The first type of model, featuring an exponential number of constraints, is solved through tailored Branch-and-Cut algorithms. In contrast, the second type of ILP model, with a polynomial number of variables and constraints, is solved using a state-of-the-art ILP solver. The latter formulation establishes a structural connection between the FB and the maximum flow interdiction problem (FI), introducing a novel approach to obtaining solutions for each problem from the other. The ILP formulations proposed for solving the FB are evaluated thanks to a theoretical analysis assessing the strength of their LP relaxations. Additionally, the exact methods presented in this paper undergo a thorough comparison through an extensive computational campaign involving a set of real-world and synthetic instances. Our tests aim to evaluate the performance of the exact algorithms and identify the features of instances that can be solved with proven optimality.
Keywords:
Combinatorial optimization
Bilevel problems
Blocker problem
Interdiction problem
Maximum-flow problem
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
View more organizations