期刊
NETWORKS
卷 40, 期 2, 页码 97-111出版社
WILEY
DOI: 10.1002/net.10039
关键词
interdiction; shortest paths; bilevel program; Benders decomposition
We study the problem of interdicting the arcs in a network in order to maximize the shortest s-t path length. Interdiction is an attack on an arc that destroys the arc or increases its effective length; there is a limited interdiction budget. We formulate this bilevel, max-min problem as a mixed-integer program (MIP), which can be solved directly, but we develop more efficient decomposition algorithms. One algorithm enhances Benders decomposition by adding generalized integer cutting planes, called supervalid inequalities (SVIs), to the master problem. A second algorithm exploits a unique set-covering master problem. Computational results demonstrate orders-of-magnitude improvements of the decomposition algorithms over direct solution of the MIP and show that SVIs also help solve the original MIP faster. (C) 2002 Wiley Periodicals, Inc.*.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据