Optimization Online


Integer Programming Formulations for Minimum Spanning Tree Interdiction

Ningji Wei(ningjiwe***at***buffalo.edu)
Jose L. Walteros(josewalt***at***buffalo.edu)
Foad Mahdavi Pajou(Foad.Mahdavi***at***umb.edu)

Abstract: We consider a two-player interdiction problem staged over a graph where the leader's objective is to minimize the cost of removing edges from the graph so that the follower's objective, i.e., 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 bi-level formulations, which are commonly solved by replacing the inner problem by its dual to produce a single level reformulation. In this paper we propose an alternative integer program derived from the combinatorial structure of the follower's solution space and prove that this new formulation yields a stronger linear relaxation than the bi-level counterpart. We also study the convex hull of the feasible solutions of the problem and identify several families of facet-defining inequalities that can be used to strengthen the proposed integer program. We then proceed by introducing an alternative 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 our approaches by solving a large collection of real-life and randomly generated instances with various configurations, analyzing and comparing the benefits of each model, and also identifying further enhancements.

Keywords: Network Interdiction, Minimum Spanning Tree, Minimum Edge Blocker Problems, Bi-level Optimization

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming

Category 3: Network Optimization


Download: [PDF]

Entry Submitted: 07/06/2019
Entry Accepted: 08/01/2019
Entry Last Modified: 07/06/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society