Optimization Online


On Integer and Bilevel Formulations for the k-Vertex Cut Problem

Fabio Furini(fabio.furini***at***dauphine.fr)
Ivana Ljubic(ivana.ljubic***at***essec.edu)
Enrico Malaguti(enrico.malaguti***at***unibo.it)
Paolo Paronuzzi(paolo.paronuzzi***at***unibo.it)

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

Download: [PDF]

Entry Submitted: 09/24/2019
Entry Accepted: 09/24/2019
Entry Last Modified: 09/24/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