On Integer and Bilevel Formulations for the k-Vertex Cut Problem
Abstract: The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.
Keywords: Vertex Cut; Mixed-Integer Linear Programming; Bilevel Programming; Branch-and-Cut algorithm.
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Network Optimization
Citation: Mathematical Programming Computation, First Online, 1-32, 2019. https://doi.org/10.1007/s12532-019-00167-1
Entry Submitted: 09/24/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|