Skip to main content
SpringerLink
Log in

A decision-theoretic approach to robust optimization in multivalued graphs

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Bellman, R. (1954). “Some Applications of the Theory of Dynamic Programming—A Review.” Journal of the Operational Research Society of America, 2(3), 275–288.

    Google Scholar 

  • Brucker, P. and H. Hamacher. (1989). “k-Optimal Solution sets for Some Polynomially Solvable Scheduling Problems.” European Journal of Operational Research, 41, 194–202.

    Article  Google Scholar 

  • Cayley, A. (1889). “A Theorem on Trees.” Quaterly Journal of Mathematics, 23, 376–378.

    Google Scholar 

  • Chegireddy, C. and H. Hamacher. (1987). “Algorithms for Finding k-best Perfect Matchings.” Discrete Applied Mathematics, 18, 155–165.

    Article  Google Scholar 

  • Chong, K.M. (1976). “An Induction Theorem for Rearrangements.” Candadian Journal of Mathematics, 28, 154–160.

    Google Scholar 

  • Climaco, J. and E. Martins. (1982). “A Bicriterion Shortest Path Algorithm.” European Journal of Operational Research, 11, 399–404.

    Article  Google Scholar 

  • D. Dubois and Ph. Fortemps (2005) “Selecting Preferred Solutions in the Minimax Approach to Dynamic Programming Problems Under Flexible Constraints” European Journal of Operational Research, 160(3), 582–598.

    Article  Google Scholar 

  • Ehrgott, M. and A. Skriver. (2003). “Solving Biobjective Combinatorial Max-Ordering Problems by Ranking Methods and a Two-Phase Approach.” European Journal of Operational Research, 147, 657–664.

    Article  Google Scholar 

  • Emelichev, V. and V. Perepelitsa. (1988). “Multiobjective Problems on the Spanning Trees of a Graph.” Soviet Math. Dokl., 37(1), 114–117.

    Google Scholar 

  • Eppstein, D. (1998). “Finding the k Shortest Paths.” SIAM Journal on Computing, 28(2), 652–673.

    Article  Google Scholar 

  • Fishburn, P. (1970). Utility Theory for Decision Making. Wiley.

  • Gabow, H. (1977). “Two Algorithms for Generating Weighted Spanning Trees in Order.” SIAM Journal on Computing, 6(1), 139–150.

    Article  Google Scholar 

  • Garey, M. and D. Johnson. (1979). Computers and Intractability. W.H. Freeman and company.

  • Gupta, S. and J. Rosenhead. (1968). “Robustness in Sequential Investment Decisions.” Management Science, 15(2), 18–29.

    Google Scholar 

  • Hamacher, H. (1995). “A Note on k-best Network Flows.” Annals of Operations Research, 57, 65–72.

    Article  Google Scholar 

  • Hamacher, H. and G. Ruhe. (1994). “On Spanning Tree Problems with Multiple Objectives.” Annals of Operations Research, 52, 209–230.

    Article  Google Scholar 

  • Hansen, P. (1980). “Bicriterion Path Problems.” In G. Fandel and T. Gal (Eds.), Multicriteria Decision Making.

  • Hardy, G.H., J.E. Littlewood, and G. Pólya. (1934). Inequalities. Cambridge University Press.

  • Herstein, I. and J. Milnor. (1953). “An Axiomatic Approach to Measurable Utility.” Econometrica, 21, 291–297.

    Article  Google Scholar 

  • R. Hites, Y. De Smet, N. Risse, M. Salazar-Neumann and P. Vincke (2006) “About the Applicability of MCDA to Some Robustness Problems” European Journal of Operational Research, 174(1), 322–332.

    Article  Google Scholar 

  • Jensen, N. (1967). “An Introduction to Bernoullian Utility Theory.” Swedish Journal of Economics, 69, 163–183.

    Article  Google Scholar 

  • O. Karasan, M. Pinar and H. Yaman (2001) “The Robust Shortest Path Problem with Interval Data” Bilkent University, Ankara, Turkey.

    Google Scholar 

  • Kostreva, M. and W. Ogryczak. (1999). “Linear Optimization with Multiple Equitable Criteria.” RAIRO Operations Research, 33, 275–297.

    Article  Google Scholar 

  • Kostreva, M., W. Ogryczak, and A. Wierzbicki. (2004). “Equitable Aggregations and Multiple Criteria Analysis.” European Journal of Operational Research, 158(2), 362–377.

    Article  Google Scholar 

  • Kouvelis, P. and G. Yu. (1997). Robust Discrete Optimization and its Applications. Kluwer Academic Publisher.

  • Kruskal, J. (1956). “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” In Proc. Am. Math. Soc.

  • Marshall, W. and I. Olkin. (1979). Inequalities: Theory of Majorization and its Applications. London: Academic Press.

  • R. Montemanni and L. M. Gambardella (2004) “An Exact Algorithm for the Robust Shortest Path Problem with Interval Data” Computers and Operations Research, 31(10) 1667–1680.

    Article  Google Scholar 

  • Murthy, I. and S. Her. (1992). “Solving Min-Max Shortest-Path Problems on a Network.” Naval Research Logistics, 39, 669–683.

    Article  Google Scholar 

  • Ogryczak, W. (2000). “Inequality Measures and Equitable Approaches to Location Problems.” European Journal of Operational Research, 122, 374–391.

    Article  Google Scholar 

  • Perny, P. and O. Spanjaard. (2003). “An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios.” In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence. pp. 469–476, Acapulco, Mexico.

  • Rosenhead, J., M. Elton, and S. Gupta. (1972). “Robustness and Optimality as Criteria for Strategic Decisions.” Operational Research Quaterly, 23(4), 413–430.

    Article  Google Scholar 

  • Roy, B. (1996). Multicriteria Methodology for Decision Aiding. Kluwer Academic Publisher.

  • Roy, B. (1998). “A Missing Link in OR-DA: Robustness Analysis.” Foundations of Computing and Decision Sciences, 23(3), 141–160.

    Google Scholar 

  • Roy, B. (2002). “Robustesse de quoi et vis-à-vis de quoi mais aussi robustesse pourquoi en aide à la décision.” Newsletter of the European Working Group Multicriteria Aid for Decisions, 3(6).

  • Sayin, S. and P. Kouvelis. (2002). “Robustness and Efficiency: A Study of the Relationship and an Algorithm for the Bicriteria Discrete Optimization Problem.” Working Paper, Olin School of Business, Washington University.

  • Sen, A. (1997). On Economic Inequality. Clarendon Press, expanded ed.

  • Shorrocks, A. (1983). “Ranking Income Distributions.” Economica, 50, 3–17.

    Article  Google Scholar 

  • Stewart, B.S. and C.C. White III. (1991). “Multiobjective A*.” Journal of the Association for Computing Machinery, 38(4), 775–814.

    Google Scholar 

  • Vincke, P. (1999a). “Robust and Neutral Methods for Aggregating Preferences into an Outranking Relation.” European Journal of Operational Research, 112(2), 405–412.

    Article  Google Scholar 

  • Vincke, P. (1999b). “Robust Solutions and Methods in Decision-Aid.” Journal of Multicriteria Decision Analysis, 8, 181–187.

    Article  Google Scholar 

  • von Neumann, J. and O. Morgenstern. (1947). Theory of Games and Economic Behavior. 2nd Ed. Princeton University Press.

  • Warburton, A. (1985). “Worst Case Analysis of Greedy and Related Heuristics for Some Min-Max Combinatorial Optimization Problems.” Mathematical Programming, 33, 234–241.

    Article  Google Scholar 

  • Weymark, J. (1981). “Generalized Gini Inequality Indices.” Mathematical Social Sciences, 1, 409–430.

    Article  Google Scholar 

  • Yaari, M. (1987). “The Dual Theory of Choice Under Risk.” Econometrica, 55, 95–115.

    Article  Google Scholar 

  • Yager, R. (1988). “On Ordered Weighted Averaging Aggregation Operators in Multicriteria Decision Making.” In IEEE Trans. Systems, Man and Cybern. vol. 18, pp. 183–190.

  • Yaman, H., O. Karaşan, and M. Pinar. (2001). “The Robust Spanning Tree Problem with Interval Data.” Operations Research Letters, 29, 31–40.

    Article  Google Scholar 

  • Yu, G. and J. Yang. (1998). “On the Robust Shortest Path Problem.” Computers and Operations Research, 25(6), 457–468.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIP6 - University of Paris VI, 4, Place Jussieu, 75252, Paris, cedex 05, France

    Patrice Perny, Olivier Spanjaard & Louis-Xavier Storme

Authors
  1. Patrice Perny
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Olivier Spanjaard
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Louis-Xavier Storme
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Perny, P., Spanjaard, O. & Storme, LX. A decision-theoretic approach to robust optimization in multivalued graphs. Ann Oper Res 147, 317–341 (2006). https://doi.org/10.1007/s10479-006-0073-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-006-0073-0

Keywords

Search

Navigation