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

Z. Caner Taşkin, J. Cole Smith

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)4-18
Number of pages15
JournalNetworks
Volume70
Issue number1
DOIs
StatePublished - Aug 2017
Externally publishedYes

Keywords

  • branch-price-cut
  • game theory
  • integer programming
  • patrol problems
  • search problems
  • symmetry

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Branch-cut-price algorithms for solving a class of search problems on general graphs'. Together they form a unique fingerprint.

  • Cite this