Optimization Online


Solving the distance-based critical node problem

Hosseinali Salemi(hosseinali.salemi***at***okstate.edu)
Austin Buchanan(buchanan***at***okstate.edu)

Abstract: In critical node problems, the task is identify a small subset of so-called critical nodes whose deletion maximally degrades a network's ``connectivity'' (however that is measured). Problems of this type have been widely studied, e.g., for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having fewer than 1,000 nodes. In this paper, we consider a variant of this problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. With the techniques developed in this paper, instances with up to 17,000 nodes can be solved exactly. We introduce two integer programming formulations for this problem (thin and path-like) and compare them with an existing recursive formulation. While the thin formulation generally has an exponential number of constraints, it admits an efficient separation routine. Also helpful is a new, more general preprocessing procedure that, on average, fixes three times as many variables than before.

Keywords: critical node; distance constraint; integer program; branch-and-cut; network interdiction; dominant; partial dominant;

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Network Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: Submitted to a journal

Download: [PDF]

Entry Submitted: 04/13/2020
Entry Accepted: 04/16/2020
Entry Last Modified: 04/13/2020

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