Geodesic
Application of a direct generalization of scalar algorithms in vector optimization on graphs
Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 110-124.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem of searching optimal paths on directed graphs with vector weights of edges. As the criterion of efficiency we use the lockout condition with respect to a binary preference relation defined on the set of paths. As the basic algorithm of vector optimisation we use the scheme of direct generalisation of scalar prototypes to the vector case. We give sufficient conditions of correctness of application of such approach. We suggest two algorithms constructed by the direct generalisation, for arbitrary graphs and graphs without cycles, prove their efficiency under the condition of asymmetry and transitivity of the preference relation. In addition, we describe a method of regulation of the cardinality of the set of effective solutions produced by the algorithm with regard to the preferences of the decision-maker. 
@article{DM_2001_13_3_a7,
     author = {Yu. V. Bugaev},
     title = {Application of a direct generalization of scalar algorithms in vector optimization on graphs},
     journal = {Diskretnaya Matematika},
     pages = {110--124},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_3_a7/}
}
TY  - JOUR
AU  - Yu. V. Bugaev
TI  - Application of a direct generalization of scalar algorithms in vector optimization on graphs
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 110
EP  - 124
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_3_a7/
LA  - ru
ID  - DM_2001_13_3_a7
ER  - 
%0 Journal Article
%A Yu. V. Bugaev
%T Application of a direct generalization of scalar algorithms in vector optimization on graphs
%J Diskretnaya Matematika
%D 2001
%P 110-124
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2001_13_3_a7/
%G ru
%F DM_2001_13_3_a7
Yu. V. Bugaev. Application of a direct generalization of scalar algorithms in vector optimization on graphs. Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 110-124. http://geodesic.mathdoc.fr/item/DM_2001_13_3_a7/

[1] Germeier Yu. V., Vvedenie v teoriyu issledovaniya operatsii, Nauka, Moskva, 1971 | MR

[2] Podinovskii V. V., Nogin V. D., Pareto-optimalnye resheniya mnogokriterialnykh zadach, Nauka, Moskva, 1982 | MR | Zbl

[3] Benaiyun R., Larichev O. I., “Lineinoe programmirovanie pri mnogikh kriteriyakh: metod ogranichenii”, Avtomatika i telemekh, 1971, no. 8, 24–31

[4] Emelichev V. A., Girlikh E., Yanushkevich O. A., “Leksikograficheskie optimumy mnogokriterialnykh zadach”, Diskretnyi analiz i issledovanie operatsii, 4:2 (1997), 3–14 | MR

[5] Ivanchev D., Kudros D., “Multicriteria optimum path problems”, Yugosl. J. Oper. Res., 1995 vol 5, no. 1, 79–93 | MR | Zbl

[6] Melamed I. I., Sigal I. Kh., Teoriya i algoritmy resheniya mnogokriterialnykh zadach kombinatornoi optimizatsii, Izd-vo VTs RAN, Moskva, 1996

[7] Kravtsov M. K., “Nerazreshimost zadach vektornoi diskretnoi optimizatsii v klasse algoritmov lineinoi svertki kriteriev”, Diskretnaya matematika, 8:2 (1996), 89–96 | MR | Zbl

[8] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, Moskva, 1978 | MR

[9] Zeleny M., Linear multiobjective programming, Springer, Berlin, 1974 | MR | Zbl

[10] Yu P. L., Zeleny M., “The set of all nondominated solutions in linear cases and a multicriteria simplex method”, J. Math. Anal. and Appl., 49 (1975), 450–468 | MR

[11] Kremar-Nozic E., “Visekriterijumsko odredivanje nedominiranih puteva izmedu zadatih cvorova u mrezi-uopstrnje Bellmanovog algoritma”, Nauc. Tehn. Pregl. VTI, 34:5 (1984), 22–24

[12] Sysoev V. V., Strukturnye i algoritmicheskie modeli avtomatizirovannogo proektirovaniya proizvodstva izdelii elektronnoi tekhniki, Voronezh. tekhnol. in-t, Voronezh, 1993

[13] Yudin D. B., Vychislitelnye metody teorii prinyatiya reshenii, Nauka, Moskva, 1989 | MR | Zbl

[14] Aizerman M. A., “Nekotorye novye zadachi obschei teorii vybora. Obzor odnogo napravleniya issledovaniya”, Avtomatika i telemekh, 1984, no. 9, 5–43 | MR | Zbl

[15] Lipskii V., Kombinatorika dlya programmistov, Mir, Moskva, 1988

[16] Kozin I. V., “Pro otsinki potuzhenosti povnoi mnozhini alternativ dlya deyakikh dvukriterialnikh zadach na grafakh”, Dokl. AN Ukr., 1993, no. 10, 108–111 | MR

[17] Emelyanov S. V., Larichev O. I., Mnogokriterialnye metody prinyatiya reshenii, Znanie, Moskva, 1985 | MR