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

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2006
Accession Number
ADA486938

Entities

People

  • Johannes Ø. Røyset
  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computer Programming
  • Computers
  • Flow Network
  • Graphs
  • Grids
  • Integer Programming
  • Interdiction
  • Laptop Computers
  • Linear Programming
  • Military Applications
  • Military Planning
  • Numbers
  • Operations Research
  • Optimization
  • Standards

Readers

  • Operations Research