Given an undirected graph, we study the capacitated vertex separator problem that asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of communication or social networks against possible viral attacks and for matrix decomposition algorithms. In this article, we provide a new bilevel interpretation of the problem and model it as a two-player Stackelberg game in which the leader interdicts the vertices (i.e., decides on the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework based on an integer programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. We also show how to extend these results to a min-max version of the problem. Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms for the capacitated vertex separator problem and is able to improve the best-known results for several difficult classes of instances. The ideas exploited in our framework can also be extended to other vertex/edge deletion/ insertion problems or graph partitioning problems by modeling them as two-player Stackel- berg games and solving them through bilevel optimization.

Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem / Furini, F.; Ljubic, I.; Malaguti, E.; Paronuzzi, P.. - In: OPERATIONS RESEARCH. - ISSN 1526-5463. - 70:4(2022), pp. 2399-2420. [10.1287/opre.2021.2110]

Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem

Furini F.
;
2022

Abstract

Given an undirected graph, we study the capacitated vertex separator problem that asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of communication or social networks against possible viral attacks and for matrix decomposition algorithms. In this article, we provide a new bilevel interpretation of the problem and model it as a two-player Stackelberg game in which the leader interdicts the vertices (i.e., decides on the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework based on an integer programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. We also show how to extend these results to a min-max version of the problem. Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms for the capacitated vertex separator problem and is able to improve the best-known results for several difficult classes of instances. The ideas exploited in our framework can also be extended to other vertex/edge deletion/ insertion problems or graph partitioning problems by modeling them as two-player Stackel- berg games and solving them through bilevel optimization.
2022
bilevel optimization; Stackelberg games; graph decomposition; branch-and-cut; Benders decomposition
01 Pubblicazione su rivista::01a Articolo in rivista
Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem / Furini, F.; Ljubic, I.; Malaguti, E.; Paronuzzi, P.. - In: OPERATIONS RESEARCH. - ISSN 1526-5463. - 70:4(2022), pp. 2399-2420. [10.1287/opre.2021.2110]
File allegati a questo prodotto
File Dimensione Formato  
Furini_Casting-Light_2022.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 1.35 MB
Formato Adobe PDF
1.35 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1673308
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact