This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Royset, J. O. Articles by Wood, R. K. Search for Related Content

Solving the Bi-Objective Maximum-Flow Network-Interdiction Problem

Operations Research Department, Naval Postgraduate School, Monterey, California 93943, USA
Operations Research Department, Naval Postgraduate School, Monterey, California 93943, USA
joroyset{at}nps.edu
kwood{at}nps.edu

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.

Key words: interdiction; maximum flow; Lagrangian relaxation; cut enumeration
History: received September 2005; revised March 2006; accepted May 2006.