An Iterative Linear Programming Approach to Solving Large Cumulative Search-Evasion Games
Loading...
Authors
Bothwell, Brian P.
Subjects
Cumulative search-evasion games
game theory
linear programming
game theory
linear programming
Advisors
Washburn, Alan R.
Date of Issue
1990-03
Date
March 1990
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Cumulative search-evasion games (CSEGs) involve two players, a searcher and an evader, who move among some finite set of cells. Neither player is aware of the other player's position during any stage of the game. When the payoff for the game is assumed to be the number of times the searcher and evader occupy the same cell, Eagle and Washburn proposed two solution techniques: one by fictitious play and the other by solving equivalent linear programming formulations. However, both have proved to be time consuming even for moderately sized problems. This thesis considers two alternate linear programming formulations for CSEGs. Since both contain a large number of variables and constraints, the linear programming problems are initially solved with many of the constraints removed. If the solution to this relaxed problem is not a feasible optimal solution, additional constraints are added and the problem is solved again. This process continues until a feasible optimal solution is found. The results from a numerical experimentation with various solution techniques are also presented.
Type
Thesis
Description
Series/Report No
Department
Operations Research
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
v, 41 p. ; ill.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.