TY - JOUR
T1 - Integer Programming Formulations for Minimum Spanning Tree Interdiction
AU - Wei, Ningji
AU - Walteros, Jose L.
AU - Pajouh, Foad Mahdavi
N1 - Publisher Copyright:
© 2021 INFORMS.
PY - 2021/9
Y1 - 2021/9
N2 - We consider a two-player interdiction problem staged over a graph where the attacker's objective is to minimize the cost of removing edges from the graph so that the defender's objective, that is, the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level r. Standard approaches for graph interdiction frame this type of problems as bilevel formulations, which are commonly solved by replacing the inner problem by its dual to produce a single-level reformulation. In this paper, we study an alternative integer program derived directly from the attacker's solution space and show that this formulation yields a stronger linear relaxation than the bilevel counterpart. Furthermore, we analyze the convex hull of the feasible solutions of the problem and identify several families of facet-defining inequalities that can be used to strengthen this integer program. We then proceed by introducing a different formulation defined by a set of so-called supervalid inequalities that may exclude feasible solutions, albeit solutions whose objective value is not better than that of an edge cut of minimum cost. We discuss several computational aspects required for an efficient implementation of the proposed approaches. Finally, we perform an extensive set of computational experiments to test the quality of these formulations, analyzing and comparing the benefits of each model, as well as identifying further enhancements. Summary of Contribution: Network interdiction has received significant attention over the last couple of decades, with a notable peak of interest in recent years. This paper provides an interesting balance between the theoretical and computational aspects of solving a challenging network interdiction problem via integer programming. We present several technical developments, including a detailed study of the problem's solution space, multiple formulations, and a polyhedral analysis of the convex hull of feasible solutions. We then analyze the results of an extensive set of computational experiments that were used to validate the effectiveness of the differentmethods we developed in this paper.
AB - We consider a two-player interdiction problem staged over a graph where the attacker's objective is to minimize the cost of removing edges from the graph so that the defender's objective, that is, the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level r. Standard approaches for graph interdiction frame this type of problems as bilevel formulations, which are commonly solved by replacing the inner problem by its dual to produce a single-level reformulation. In this paper, we study an alternative integer program derived directly from the attacker's solution space and show that this formulation yields a stronger linear relaxation than the bilevel counterpart. Furthermore, we analyze the convex hull of the feasible solutions of the problem and identify several families of facet-defining inequalities that can be used to strengthen this integer program. We then proceed by introducing a different formulation defined by a set of so-called supervalid inequalities that may exclude feasible solutions, albeit solutions whose objective value is not better than that of an edge cut of minimum cost. We discuss several computational aspects required for an efficient implementation of the proposed approaches. Finally, we perform an extensive set of computational experiments to test the quality of these formulations, analyzing and comparing the benefits of each model, as well as identifying further enhancements. Summary of Contribution: Network interdiction has received significant attention over the last couple of decades, with a notable peak of interest in recent years. This paper provides an interesting balance between the theoretical and computational aspects of solving a challenging network interdiction problem via integer programming. We present several technical developments, including a detailed study of the problem's solution space, multiple formulations, and a polyhedral analysis of the convex hull of feasible solutions. We then analyze the results of an extensive set of computational experiments that were used to validate the effectiveness of the differentmethods we developed in this paper.
KW - bilevel optimization
KW - minimum edge blocker problems
KW - minimum spanning tree
KW - network interdiction
UR - http://www.scopus.com/inward/record.url?scp=85123679701&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85123679701&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2020.1018
DO - 10.1287/ijoc.2020.1018
M3 - Article
AN - SCOPUS:85123679701
SN - 1091-9856
VL - 33
SP - 1461
EP - 1480
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 4
ER -