A decision-theoretic approach to robust optimization in multivalued graphs

Patrice Perny, Olivier Spanjaard and Louis-Xavier Storme

Annals of Operations Research, 2006, vol. 147, issue 1, 317-341

Abstract: This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach. Copyright Springer Science + Business Media, LCC 2006

Keywords: Robust optimization; Multicriteria optimization; Lorenz optima; k best solutions; Minimum spanning tree; Shortest path (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-0073-0 (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:147:y:2006:i:1:p:317-341:10.1007/s10479-006-0073-0

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

DOI: 10.1007/s10479-006-0073-0

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 ().