Valid inequalities for the $$\beta $$ -edge disruptor problem

Sheng-Jie Chen, Guang-Ming Li (), Liang Chen, Caixia Kou and Yu-Hong Dai
Additional contact information
Sheng-Jie Chen: Chinese Academy of Sciences
Guang-Ming Li: Beijing University of Posts and Telecommunications
Liang Chen: Chinese Academy of Sciences
Caixia Kou: Beijing University of Posts and Telecommunications
Yu-Hong Dai: Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2025, vol. 50, issue 4, No 7, 29 pages

Abstract: Abstract The $$\beta $$ -edge disruptor problem ( $$\beta $$ -EDP) aims to identify the minimum weight of edges in an undirected graph, whose removal results in a specific degradation of graph connectivity. This problem is crucial for assessing network vulnerability against disruptive events, providing valuable insights for network security and risk management. Due to its NP-hard nature, solving the problem to optimality is highly challenging. In this paper, we shall provide an efficient algorithm for precisely solving the integer programming (IP) model for the $$\beta $$ -EDP. Firstly, the mixing technique is adapted to derive a family of mixing inequalities for the IP model. Secondly, we introduce the definition of “cover” within the context of the $$\beta $$ -EDP, and propose a family of cover inequalities. We also apply the sequential lifting technique to strengthen the cover inequalities. Moreover, the separation problems associated with both families of inequalities are investigated, with efficient separation procedures developed. Finally, we present specialized cutting plane approaches based on the proposed inequalities. The computational results showcase the effectiveness of integrating our proposed inequalities within an IP solver.

Keywords: Vulnerability assessment; Integer programming; Valid inequality; Separation; 90C35; 90C10; 90C57 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01366-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:4:d:10.1007_s10878-025-01366-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01366-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().