  


Solving the distancebased critical node problem
Hosseinali Salemi(hosseinali.salemiokstate.edu) Abstract: In critical node problems, the task is identify a small subset of socalled 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 pathlike) 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; branchandcut; network interdiction; dominant; partial dominant; Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Network Optimization Category 3: Integer Programming (01 Programming ) Citation: Submitted to a journal Download: [PDF] Entry Submitted: 04/13/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  