期刊
INFORMS JOURNAL ON COMPUTING
卷 19, 期 2, 页码 175-184出版社
INFORMS
DOI: 10.1287/ijoc.1060.0191
关键词
interdiction; maximum flow; Lagrangian relaxation; cut enumeration
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据