Branch‐cut‐price algorithms for solving a class of search problems on general graphs
Abstract
We consider graph search problems involving an intruder and mobile searchers. The graph consists of nodes on which the intruder and searchers may be located, and edges on which these entities travel. Associated with each node is a set of nodes that are visible from that node. The goal is to find the minimum number of searchers needed to detect the intruder within a given time limit. We investigate three variants of the graph search problem: (i) a hide‐and‐seek problem, in which a stationary intruder “hides” at an unknown node, (ii) a pursuit‐evasion problem, in which the intruder moves among the nodes to avoid being detected, and (iii) a patrol problem, which is similar to the pursuit‐evasion problem except that searchers patrol the graph in repeated circuits to seek intruders. Our contribution provides exponential‐size set‐covering formulations for these problems, along with a class of branch‐cut‐price algorithms tailored for solving them. These algorithms leverage results from the orienteering literature to solve pricing problems related to searcher routes. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 4–18 2017
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 17, 2017
- Source ID
- 10.1002/net.21740
Entities
People
- J. Cole Smith
- Z. Caner Taşkin
Organizations
- Air Force Office of Scientific Research
- Boğaziçi University
- Clemson University
- Defense Threat Reduction Agency
- Office of Naval Research