Verified methods for computing Pareto sets: General algorithmic analysis
Boglárka G. Tóth ; Vladik Kreinovich
International Journal of Applied Mathematics and Computer Science, Tome 19 (2009), p. 369-380 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In many engineering problems, we face multi-objective optimization, with several objective functions f₁,...,fₙ. We want to provide the user with the Pareto set-a set of all possible solutions x which cannot be improved in all categories (i.e., for which fj(x')≥fj(x) for all j and fj(x)>fj(x) for some j is impossible). The user should be able to select an appropriate trade-off between, say, cost and durability. We extend the general results about (verified) algorithmic computability of maxima locations to show that Pareto sets can also be computed.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:207942 
@article{bwmeta1.element.bwnjournal-article-amcv19i3p369bwm,
     author = {Bogl\'arka G. T\'oth and Vladik Kreinovich},
     title = {Verified methods for computing Pareto sets: General algorithmic analysis},
     journal = {International Journal of Applied Mathematics and Computer Science},
     volume = {19},
     year = {2009},
     pages = {369-380},
     zbl = {1300.90041},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv19i3p369bwm}
}

Boglárka G. Tóth; Vladik Kreinovich. Verified methods for computing Pareto sets: General algorithmic analysis. International Journal of Applied Mathematics and Computer Science, Tome 19 (2009) pp. 369-380. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv19i3p369bwm/

[000] Aberth, O. (2007). Introduction to Precise Numerical Methods, Academic Press, San Diego, CA. | Zbl 1127.65001

[001] Beeson, M. (1978). Some relations between classical and constructive mathematics, Journal of Symbolic Logic 43(2): 228-246. | Zbl 0393.03041

[002] Beeson, M. (1985). Foundations of Constructive Mathematics: Metamathematical Studies, Springer, Berlin/Heidelberg/New York, NY. | Zbl 0565.03028

[003] Bishop, E. and Bridges, D.S. (1985). Constructive Analysis, Springer-Verlag, Berlin/Heidelberg/New York, NY. | Zbl 0656.03042

[004] Fernández, J. and Tóth, B. (2006). Obtaining the efficient set of biobjective competitive facility location and design problems, Proceedings of the 21th European Conference on Operations Research EURO XXI, Reykjavík, Iceland, pp. T-28.

[005] Fernández, J. and Tóth, B. (2007). Obtaining an outer approximation of the efficient set of nonlinear biobjective problems, Journal of Global Optimization 38(2): 315-331. | Zbl 1172.90482

[006] Fernández, J. and Tóth, B. (2009). Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods, Computational Optimization and Applications 42(3):393-419. | Zbl 1211.90208

[007] Fernández, J., Tóth, B., Plastria, F. and Pelegrín, B. (2006). Reconciling franchisor and franchisee: A planar multiobjective competitive location and design model, in A. Seeger (Ed.) Recent Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 563, Berlin/Heidelberg/New York, NY, pp. 375-398. | Zbl 1101.90059

[008] Figueira, J., Greco, S. and Ehrgott, M. (Eds.) (2004). Multiple Criteria Decision Analysis: State of the Art Surveys, Kluwer, Dordrecht. | Zbl 1060.90002

[009] Kreinovich, V. (1975). Uniqueness implies algorithmic computability, Proceedings of the 4th Student Mathematical Conference, Leningrad, USSR, pp. 19-21, (in Russian).

[010] Kreinovich, V. (1979). Categories of Space-Time Models, Ph.D. dissertation, Institute of Mathematics, Soviet Academy of Sciences, Siberian Branch, Novosibirsk, (in Russian).

[011] Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht. | Zbl 0945.68077

[012] Kushner, B.A. (1985). Lectures on Constructive Mathematical Analysis, American Mathematical Society, Providence, RI. | Zbl 0547.03040

[013] Nachbar, J.H. and Zame, W.R. (1996). Non-computable strategies and discounted repeated games, Economic Theory 8(1): 103-122. | Zbl 0852.90146

[014] Nickel, S. and Puerto, J. (2005). Location Theory: A Unified Approach, Springer-Verlag, Berlin. | Zbl 1229.90001

[015] Ruzika, S. and Wiecek, M.M. (2005). Approximation methods in multiopbjective programming. Journal of Optimization Theory and Applications 126(3): 473-501. | Zbl 1093.90057

[016] Tóth, B. and Fernández, J. (2006). Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods, Proceedings of the 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics SCAN'06, Duisburg, Germany. | Zbl 1211.90208