Integer Programming Formulations for Min Edge Blocker Problem Respect to Minimum Spanning Tree
MetadataShow full item record
Considering a graph G(V,E), there is a weight w on each edge in E, and a cost c to remove (or block) it. We can spend certain cost to remove a subset of edges S, which will in turn increase the weight of minimum spanning tree on the remaining graph G' = (V,E–S). The min edge blocker problem (MEBP) is about minimizing the total cost of removing S when ensure the weight of the minimum spanning tree on the remaining graph is greater than a given requirement r. This problem is known as NP-Hard. In this paper we developed two integer programming formulations based on multi-commodity flow and spanning tree retaining, a cuts generation algorithm based on ST and 1-tree constraints, two light subgraph (a concept generalized from ST and 1-tree constraints) based formulations, and a supervalid constraints based algorithm. The inherent relations between algorithms based on multi-commodity, ST constraint and supervalid cuts are analyzed. We proved some polyhedral properties of the convex hull induced by feasible solutions to MEBP and identified facet-inducing inequalities for the polytope. Finally, we provided the computational results of those algorithms, and the enumeration algorithm based on supervalid cuts is clear better than other algorithms in most cases.