Optimization Online


Optimizing Placement of Stationary Monitors

Andrew Romich(aromich222***at***gmail.com)
Guanghui Lan(glan***at***ise.ufl.edu)
J. Cole Smith(cole***at***ise.ufl.edu)

Abstract: We examine the problem of placing stationary monitors in a continuous space, with the goal of minimizing an adversary's maximum probability of traversing an origin-destination route without being detected. The problem arises, for instance, in defending against the transport of illicit material through some area of interest. In particular, we consider the deployment of monitors whose probability of detecting an intruder is a function of the distance between the monitor and the intruder. Under the assumption that the detection probabilities are mutually independent, we construct a two-stage mixed-integer nonlinear programming formulation for the problem. We first provide an algorithm that optimally locates monitors in a continuous space. Then, we examine this problem for the case in monitor locations are restricted to two different discretized subsets of continuous space. Our analysis provides optimization algorithms for each case, and derives bounds on the worst-case optimality gap between the restrictions and the initial (continuous-space) problem. Empirically, we show that we can obtain discretized solutions whose worst-case and actual optimality gaps are well within practical limits.


Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Network Optimization


Download: [PDF]

Entry Submitted: 10/24/2012
Entry Accepted: 10/24/2012
Entry Last Modified: 10/24/2012

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