Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 4, 2021, P. 90-116
UDC 519.816+519.854.2
A. O. Zakharov and Yu. V. Kovalenko
The reduction of the Pareto set of a special structure in bicriteria discrete problems
Abstract:
We investigate bicriteria discrete optimization problems in the context of the axiomatic approach of the Pareto set reduction. The degree of the reduction with respect to values of the coefficient of compromise is evaluated for special structures and general case of the Pareto set. The results are applied to the set covering problem and vehicle routing problems.
Illustr. 4, bibliogr. 19.
Keywords: discrete optimization, bicriteria problem, the Pareto set reduction, preference relation of the decision maker.
DOI: 10.33048/daio.2021.28.712
Aleksey O. Zakharov 1
Yulia V. Kovalenko 2
1. St. Petersburg State University,
7–9 Universitetskaya Embankment, 199034 St. Petersburg, Russia
2. Sobolev Institute of Mathematics,
13 Pevtsov Street, 644099 Omsk, Russia
e-mail: zakh.alexey@gmail.com, julia.kovalenko.ya@yandex.ru
Received April 19, 2021
Revised June 8, 2021
Accepted June 10, 2021
References
[1] O. I. Larichev, Decision-Making Theory and Methods, as well as a Chronicle of Events in Magical Lands (Logos, Moscow, 2006) [Russian].[2] A. V. Lotov and I. I. Pospelova, Multi-Criteria Decision Making Problems (MAKS Press, Moscow, 2008) [Russian].
[3] A. B. Petrovsky, Decision Making Theory (Akademiya, Moscow, 2009) [Russian].
[4] A. Ishizaka and P. Nemery, Multi-Criteria Decision Analysis: Methods and Software (Wiley, Hoboken, NJ, 2013).
[5] M. Ehrgott, J. L. Figueira, and S. Greco, Trends in Multiple Criteria Decision Analysis (Springer, New York, 2010).
[6] S. Greco, M. Ehrgott, and J. L. Figueira, Multiple Criteria Decision Analysis: State of the Art Surveys (Springer, New York, 2016).
[7] O. I. Larichev, Verbal Analysis of Solutions (Nauka, Moscow, 2006) [Russian].
[8] V. D. Nogin, Pareto Set Reduction: An Axiomatic Approach (FIZMATLIT, Moscow, 2016) [Russian].
[9] A. O. Zakharov and Yu. V. Kovalenko, Reduction of the Pareto set in bicriteria Asymmetric Traveling Salesman Problem, in Optimization Problems and Their Applications (Proc. 7th Int. Conf. OPTA 2018, Omsk, Russia, July 8–14, 2018) (Springer, Heidelberg, 2018), pp. 93–105 (CCIS, Vol. 871).
[10] A. O. Zakharov and Yu. V. Kovalenko, Construction and reduction of the Pareto set in Asymmetric Travelling Salesman Problem with two criteria, Vestn. S. Petersburg Univ., Appl. Math. Comput. Sci. Control Processes 14 (4), 378–392 (2018).
[11] A. O. Zakharov and Yu. V. Kovalenko, Structures of the Pareto set and their reduction in bicriteria discrete problems, J. Phys., Conf. Series 1260 (8), 082007:1–082007:8 (2019).
[12] N. Christofides, Graph Theory. An Algorithmic Approach (Academic Press, London, 1975).
[13] A. V. Eremeev, L. A. Zaozerskaya, and A. A. Kolokolov, A set covering problem: Complexity, algoritms, experimental research, Diskretn. Anal. Issled. Oper., Ser. 2, 7 (2), 22–46 (2000) [Russian].
[14] M. I. Nechepurenko, V. K. Popkov, S. M. Majnagashev, S. B. Kaul’, V. A. Proskuryakov, V. A. Kohov, and A. B. Gryzunov, Algorithms and Programs for Solving Problems on Graphs and Networks (Nauka, Novosibirsk, 1990) [Russian].
[15] A. A. Kolokolov and L. A. Zaozerskaya, Solving a bicriteria problem of optimal service centers location, J. Math. Model. Algorithms 12, 105–116 (2013).
[16] J. Saksena, Mathematical model for scheduling clients through welfare agencies, J. Can. Oper. Res. Soc. 8, 185–200 (1970).
[17] A. Henry-Labordere, The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem, Rev. Franç. Inform. Rech. Opér. 3 (B-2), 43–49 (1969).
[18] M. Yu. Khachai and E. D. Neznakhina, Approximation schemes for the Generalized Traveling Salesman Problem, Tr. Inst. Mat. Mekh. UrO RAN 22 (3), 283–292 (2016) [Russian] [Proc. Steklov Inst. Math. 299 (1), 97–105 (2017)].
[19] A. G. Chentsov, M. Yu. Khachai, and D. M. Khachai, An exact algorithm with linear complexity for a problem of visiting megalopolises, Tr. Inst. Mat. Mekh. UrO RAN 21 (3), 309–317 (2015) [Russian] [Proc. Steklov Inst. Math. 295 (1), 38–46 (2016)].
