  


On Integer and Bilevel Formulations for the kVertex Cut Problem
Fabio Furini(fabio.furinidauphine.fr) 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 kvertex 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 polytime separation procedures and design the respective branchandcut 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 twophase 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 stateoftheart exact methods from the literature. Keywords: Vertex Cut; MixedInteger Linear Programming; Bilevel Programming; BranchandCut algorithm. Category 1: Combinatorial Optimization Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Category 3: Network Optimization Citation: Mathematical Programming Computation, First Online, 132, 2019. https://doi.org/10.1007/s12532019001671 Download: [PDF] Entry Submitted: 09/24/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  