Network interdiction via a critical disruption path: branch-and-price algorithms

DOI10.1016/j.cor.2013.04.016zbMath1348.90596OpenAlexW1982943536MaRDI QIDQ336604

Steffen Rebennack, Donatella Granata, Gregory Steeger

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2013.04.016

zbMATH Keywords

NP-completenessbranch-and-pricemixed-integer linear programmingnetwork interdictioncuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (13)

Network interdiction through length-bounded critical disruption paths: a bi-objective approach ⋮ A mixed-integer programming approach for locating jamming devices in a flow-jamming attack ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ The connected critical node problem ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ The stochastic critical node problem over trees ⋮ Finding the most degree-central walks and paths in a graph: exact and heuristic approaches ⋮ A study of network violator interception based on a reliable game model ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ A bi-level model and memetic algorithm for arc interdiction location-routing problem ⋮ Optimal detection of critical nodes: improvements to model structure and performance ⋮ Sequential Shortest Path Interdiction with Incomplete Information ⋮ Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Identifying sets of key players in a social network
• Detecting critical nodes in sparse graphs
• Deterministic network interdiction
• Finding the most vital arcs in a network
• A cutting plane algorithm for computing \(k\)-edge survivability of a network
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Interior point stabilization for column generation
• Solving the Bi-Objective Maximum-Flow Network-Interdiction Problem
• Maximal Flow Through a Network
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Shortest-path network interdiction
• Selected Topics in Column Generation
• Removing Arcs from a Network
• Optimal interdiction of a supply network

This page was built for publication: Network interdiction via a critical disruption path: branch-and-price algorithms