Abstract
This paper describes theNeighbourhood Search, an effectivemethod that we suggest for constructing Pareto sets in multiple objective problems with conegenerated orders. TheNeighbourhood Search is then applied to discounted Markov Decision Processes, resulting in original statements about topological properties of Pareto sets. A meaningful example is also presented.
Similar content being viewed by others
References
Altman E (1999) Constrained Markov decision processes. Chapman and Hall/CRC, Boca Raton
Armand P (1993) Finding all maximal efficient faces in multiobjective linear programming. Math Programm 61:357–375
Armand P, Malivert C (1991) Determination of the efficient set in multiobjective linear programming. J Optim Theory Appl 70:467–488
Bertsekas DP (2003) Convex analysis and optimization. Athena Scientific, Belmont
Bertsekas DP, Shreve SE (1978) Stochastic optimal control. Academic Press, N.Y-S.Francisco-London
Chen RC, Blankenship GL (2004) Dynamic programming equations for discounted constrained stochastic control. IEEE Trans Aut Control 49:699–709
Dattorro J (2005) Convex optimization and eucledean distance geometry. Meboo Publishing, USA
Dynkin EB, Yushkevich AA (1979) Controlled Markov processes and their applications. Springer, Berlin Heidelberg New York
Ehrgott M (2000) Multicriteria optimization. Lecture Notes in economics and mathematical systems, vol 491. Springer, Berlin Heidelberg New York
Feinberg EA (2000) Constrained discounted Markov decision processes and Hamiltonian cycles. Math Oper Res 25:130–140
Feinberg EA, Shwartz A (1996) Constrained discounted dynamic programming. Math Oper Res 21:922–945
Feinberg E, Piunovskiy A (2002) Nonatomic total rewards Markov decision processes with multiple criteria. J Math Anal Appl 273:93–111
Furukawa N (1980) Vector-valued Markovian decision processes with countable state space. In: Hartley R, Thomas LC, White DJ (eds) Recent Developments in Markov decision Processes. Academic Press, London New York, pp. 205–223
Ghosh MK (1990) Markov decision processes with multiple costs. Oper Res Lett 9:257–260
Hernandez-Lerma O, Romera R (2004) The scalarization approach to multiobjective Markov control problems: why does it work? Appl Math Optim 50:279–293
Heyman DP, Sobel MJ (1984) Stochastic models in operations research Stochastic optimization, vol II. McGrow-Hill Book Company, New York
Kaliszewski I (1994) Quantitative Pareto analysis by cone separation technique. Kluwer, Boston
Magaril-Il’yaev GG, Tikhomirov VM (2003) convex analysis: theory and applications. Amer Math Soc Providence
Meyer P-A (1966) Probability and potentials. Blaisdell. Waltham, Massachusetts-Toronto-London
Micevski T, Kuczera G, Coombes PJ (2002) Markov model for stormwater pipe deterioration. J Infrastruct Syst 8:49–56
Piunovskiy AB (1997) Optimal control of random sequences in problems with constraints. Kluwer, Dordrecht
Piunovskiy A (1998) Controlled random sequences: methods of convex analysis and problems with functional constraints. Russ Math Surveys 56:1233–1293
Piunovskiy A, Mao X (2000) Constrained Markovian decision processes: the dynamic programming approach. Oper Res Lett 27:119–126
Preparata FP, Shamos MI (1993) Computational geometry. Springer, Berlin Heidelberg New York
Puterman ML (1994) Markov decision processes. Wiley, New York
Stoer J, Witzgall C (1970) Convexity and optimization in finite dimensions. Springer, Berlin Heidelberg New York
Wakuta K (1996) A new class of policies in vector-valued Markov decision processes. J Math Anal Appl 202:623–628
Wakuta K (1998) Discounted cost Markov decision processes with a constraint. Prob Eng Inf Sci 12:177–187
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dorini, G., Pierro, F.D., Savic, D. et al. Neighbourhood Search for constructing Pareto sets. Math Meth Oper Res 65, 315–337 (2007). https://doi.org/10.1007/s00186-006-0117-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-006-0117-x