Solving the bi-objective maximum-flow network-interdiction problem

We describe a new algorithm for computing the efficient frontier of the ‘bi–objective maximum–flow network–interdiction problem.’ In this problem, an ‘interdictor’ seeks to interdict (destroy) a set of arcs in a capacitated network that are Pareto–optimal with respect to two objectives, minimizing total interdiction cost and minimizing maximum flow. The algorithm identifies these solutions through a sequence of single–objective problems solved using Lagrangian relaxation and a specialized branch–and–bound algorithm. The Lagrangian problems are simply max–flow min–cut problems, while the branch–and–bound procedure partially enumerates s–t cuts. Computational tests reveal the new algorithm to be one to two orders of magnitude faster than an algorithm that replaces the specialized branch–and–bound algorithm with a standard integer–programming solver.