Optimization problems involving collections of dependent objects

David Roberts (), Charles Isbell () and Michael Littman ()

Annals of Operations Research, 2008, vol. 163, issue 1, 255-270

Abstract: We describe a class of problems motivated by numerous real-world applications where there is a collection of objects that have both a cost and a value, but where some of those objects depend upon other objects to obtain their full value. Applications include finding an optimal order for transferring files under threat of system failure, ordering sequences of actions by a heterogeneous team of agents or robots, picking an optimal set of products to store in a warehouse, selecting courses to take at a university, or picking what products to cut from production. We formalize the problem of representing objects and their dependence relationships as a directed acyclic graph (DAG). We define simple formulae for calculating the utility of both sets and sequences of graph vertices. We motivate, using real-world examples, a taxonomy of problems associated with the model we present. We also prove that two variants of problems associated with our formalism are NP-hard, and present an efficient algorithm for solving a restricted version of a third problem. Copyright Springer Science+Business Media, LLC 2008

Date: 2008
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-008-0350-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:163:y:2008:i:1:p:255-270:10.1007/s10479-008-0350-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-008-0350-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().