Back to search

Monterey, California. Naval Postgraduate School

Solution of large-scale allocation problems with partially observable outcomes

Abstract

dc:description.abstract

We develop methods for optimally solving problems that require allocating scarce resources among activities that either gather information on a set of objects or take actions to change their status. Also, the information we gather on the outcomes of the actions we take may be erroneous. The latter situation is called partial observability, and methodology available prior to this dissertation is combinatorially intractable for problems with more than one object. We use two previously-uncombined methods - linear programming (LP) and partially observable Markov decision processes (POMDPs) - to construct a decomposition procedure to solve the resulting large-scale allocation problem with partially observable outcomes. We show theoretically that this procedure is both optimal and finite; in addition, we develop improvements to the procedure that reduce runtimes on test problems by 95%. We demonstrate the procedure on a small targeting problem with a known analytical solution, as well as a large- scale military example concerned with allocating aircraft sorties, weapons, and bomb-damage assessment sensors to targets. Finally, we develop analytical bounds on the expected objective function values of a related allocation problem with more stringent resource constraints, and present a simulation-based approach to estimate the distributions of the outcomes for that model.

Degree

thesis:*
Name thesis:degree_name
Ph.D in Operations Research
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Operations Research
Department dc:contributor.department
Department of Operations Research
Grantor dc:publisher
Monterey, California. Naval Postgraduate School
Year dc:date.issued
1998

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yost, Kirk A.
Advisors dc:contributor.advisor
  • Washburn, Alan R.
  • Owen, Guillermo

Rights

dc:rights
Statement dc: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.
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/8979

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-20
Source record
OAI-PMH GetRecord
related terms
citation

Yost, Kirk A.. Solution of large-scale allocation problems with partially observable outcomes. Doctoral thesis, Monterey, California. Naval Postgraduate School, 1998. https://hdl.handle.net/10945/8979