Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 97, Issue -, Pages 48-57Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2018.04.012
Keywords
Network connectivity; Network interdiction; Mixed integer linear programming
Ask authors/readers for more resources
The minimum connectivity interdiction problem seeks to remove at most k nodes from an undirected graph, such that a connectivity measure of the remaining subgraph is minimized. Examples of connectivity measures of a graph include the number of connected pairs of nodes, the size of the largest connected component, and the inverse of the number of connected components. This paper proposes improvements to mixed integer linear programming formulations from the literature. Improvements correspond to the construction of formulations with either a smaller number of constraints, or stronger formulations with increased sparsity of constraint matrices. In addition, two of the discussed problem formulations are demonstrated to provide the same value of linear programming relaxation and hence can be called equivalent. Computational experiments demonstrate that improved formulations allow us to solve some of the considered problem instances up to an order of magnitude times faster than using the recent benchmark. (C) 2018 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available