期刊
NETWORKS
卷 69, 期 4, 页码 367-377出版社
WILEY
DOI: 10.1002/net.21732
关键词
maximum flow network interdiction; valid inequality; valid separation; extended formulation; integrality gap
We consider the maximum flow network interdiction problem in its cardinality case. There is an integer programming model for this problem by Wood (Math Comput Model 17 (1993), 1-18). Two types of valid inequalities have also been proposed (Altner et al., Oper Res Lett 38 (2010), 33-38 and Wood, Math Comput Model 17 (1993), 1-18) to strengthen the LP relaxation of the integer model. However, due to their combinatorial nature, the number of these inequalities are exponential. Here, we present an equivalent reformulation (extended formulation) for this problem which has a polynomial number of constraints. We also introduce new valid inequalities, and show that the corresponding reformulation of the LP relaxation of the integer model augmented with these inequalities, significantly decreases the integrality gap for a class of network interdiction problems with proven large integrality gaps. Numerical results for some benchmark as well as randomly generated instances are also reported. (c) 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 367-377 2017
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据