Branch-cut-price algorithms for solving a class of search problems on general graphs

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.