Geodesic
Approximating the convex Edgeworth–Pareto hull in integer multi-objective problems with monotone criteria
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 10, pp. 1765-1778 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A method for the iterative polyhedral approximation of the convex Edgeworth–Pareto hull is proposed and examined experimentally. This method is designed for integer multi-objective problems with monotone objective functions and constraints given by a computational module. It is based on a synthesis of the ideas of the branch-and-bound method and the methods for the polyhedral approximation of convex bodies. A sequence of interior and exterior polyhedral sets is constructed so as to approximate the Edgeworth–Pareto hull to the desired accuracy. The results of the theoretical and experimental analyses of the proposed method are presented. 
@article{ZVMMF_2009_49_10_a3,
     author = {A. I. Pospelov},
     title = {Approximating the convex {Edgeworth{\textendash}Pareto} hull in integer multi-objective problems with monotone criteria},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1765--1778},
     year = {2009},
     volume = {49},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_10_a3/}
}
TY  - JOUR
AU  - A. I. Pospelov
TI  - Approximating the convex Edgeworth–Pareto hull in integer multi-objective problems with monotone criteria
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 1765
EP  - 1778
VL  - 49
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_10_a3/
LA  - ru
ID  - ZVMMF_2009_49_10_a3
ER  - 
%0 Journal Article
%A A. I. Pospelov
%T Approximating the convex Edgeworth–Pareto hull in integer multi-objective problems with monotone criteria
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 1765-1778
%V 49
%N 10
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_10_a3/
%G ru
%F ZVMMF_2009_49_10_a3
A. I. Pospelov. Approximating the convex Edgeworth–Pareto hull in integer multi-objective problems with monotone criteria. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 10, pp. 1765-1778. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_10_a3/

[1] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, M., 2007

[2] Yu G., Industrial applications of combinatorial optimization, Kluwer Acad. Publs., Boston, 1998 | MR

[3] Podinovskii V. V., Nogin V. D., Pareto-optimalnye resheniya mnogokriterialnykh zadach, Fizmatlit, M., 2007

[4] Melamed I. I., Sigal I. Kh., “Issledovanie lineinoi svertki kriteriev v mnogokriterialnom diskretnom programmirovanii”, Zh. vychisl. matem. i matem. fiz., 35:8 (1995), 1260–1270 | MR | Zbl

[5] Melamed I. I., Sigal I. Kh., Teoriya i algoritmy resheniya mnogokriterialnykh zadach kombinatornoi optimizatsii, VTs RAN, M., 1996

[6] Sigal I. Kh., “Algoritmy dlya resheniya bikriterialnoi zadachi kommivoyazhera bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 34:1 (1994), 44–57 | MR | Zbl

[7] Ehrgott M., Gandibleux X., An annotated bibliography of multiobjective combinatorial optimization, Techn. Rept 62: Wirtschaftsmathematik, 2000

[8] Melamed I. I., Sigal I. I., Vladimirova N. Yu., “Issledovanie lineinoi svertki kriteriev v bikriterialnoi zadache o rantse”, Zh. vychisl. matem. i matem. fiz., 39:5 (1999), 753–758 | MR | Zbl

[9] Gandibleux X., Klamroth K., Cardinality bounds for multiobjective knapsack problems, Techn. Rept, Inst. of Appl. Math., Univ. of Erlangen-Nuremberg, Germany, 2006

[10] Hamacher H. W., Pedersen C. R., Ruzika S., “Finding representative systems for discrete bicriteria optimization problems by box algorithms”, Operat. Res. Letts, 35 (2007), 336–344 | DOI | MR | Zbl

[11] Schweigert D., “Vector-weighted matchings”, Math. Appl., 329, Kluwer Acad. Publ., Dordrecht, 1995, 267–276 | MR | Zbl

[12] Glover F., Laguna M., Tabu Search, Kluwer Acad. Publ., Dordrecht, 1997 | MR

[13] Zitzler E., Thiele L., “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach”, IEEE Trans. Evolution. Comput., 3:4 (1999), 257–271 | DOI

[14] Lotov A. V., Miettinen K., “Visualizing the Pareto frontier”, Multiobjective Optimizat. Interact. and Evolutionary Approach., Lect. Notes in Comput. Sci., 5252, Springer, Berlin–Heidelberg, 2008, 213–244

[15] Gusev D. V., Lotov A. B., “Metody podderzhki prinyatiya reshenii v zadache konechnogo vybora”, Issled. operatsii. Modeli, sistemy, resheniya, VTs RAN, M., 1994, 15–43

[16] Bushenkov V. A., Lotov A. B., Metody postroeniya i ispolzovaniya obobschennykh mnozhestv dostizhimosti, VTs AN SSSR, M., 1982

[17] Kamenev G. K., Optimalnye adaptivnye metody poliedralnoi approksmatsii vypuklykh tel, VTs RAN, M., 2007 | MR

[18] Lotov A. B., Bushenkov V. A., Kamenev G. K., Metod dostizhimykh tselei. Matematicheskie osnovy i ekologicheskie prilozheniya, Edvin Mellen Press, Nyu-Iork, 1999

[19] Lotov A. B., Bushenkov V. A., Kamenev G. K., Chernykh O. L., Kompyuter i poisk kompromissa. Metod dostizhimykh tselei, Nauka, M., 1997

[20] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps. Approximation and visualization of Pareto frontier, Kluwer Acad. Publ., Boston, 2004 | MR | Zbl

[21] Burmistrova L. V., Efremov R. V., Lotov A. B., “Metodika vizualnoi podderzhki prinyatiya reshenii i ee primenenie v sistemakh upravleniya vodnymi resursami”, Izv. RAN. Teoriya i sistemy upravleniya, 2002, no. 5, 89–100

[22] Jankowski P., Lotov A., Gusev D., “Multiple criteria trade-off approach to spatial decision making”, Spatial Multicriteria Decision Making and Analys: A Geograph. Inform. Sci. Approach, VT, Ashgate, Brookfield, 1999, 127–148

[23] Soloveichik D., Ben-Aderet N., Grinman M., Lotov A., “Multi-objective optimization and marginal abatement cost in the electricity sector – an Israeli case study”, Europ. J. Operat. Res., 140:3 (2002), 571–583 | DOI

[24] Lotov A. V., Bushenkov V. A., Kamenev G. K., Feasible goals method – Search for smart decisions, Comput. Centre RAS, M., 2001 | Zbl

[25] Evdokimov M..V., Mednitskii V. G., Sigal I. Kh., “Bikriterialnaya zadacha pereoborudovaniya proizvodstva”, Izv. RAN. Teoriya i sistemy upravleniya, 2001, no. 5, 90–96 | MR | Zbl

[26] Badri M. A., Mortagy A. K., Alsayed C. A., “A multi-objective model for locating fire stations”, Europ. J. Operat. Res., 110:2 (1998), 243–260 | DOI | Zbl

[27] Jaszkiewicz A., A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm, Techn. Rept. RA-003/01, Inst. Comput. Sci., Poznan Univ. of Technol., Poznan, Poland, 2001

[28] Smith B. M., Wren A., “A bus crew scheduling system using a set covering formulation”, Transport. Res. A, 22 (1988), 97–108 | DOI

[29] Jenkins L., “A bicriteria knapsack program for planning remediation of contaminated lightstation sites”, Europ. J. Operat. Res., 127:2 (2002), 427–433 | DOI

[30] Hamacher H. W., Ruzika S., Tanatmis A., Acquisition prioritization: A multicriteria approach based on a case study, Techn. Rept. 100/2006, Univ. of Kaiserslautern, Dept of Math., 2006

[31] Preparata F., Sheimos M., Vychislitelnaya geometriya: vvedenie, Mir, M., 1989 | MR | Zbl

[32] Lotov A. V., Bourmistrova L. V., Efremov R. V. et al., “Experience of model integration and Pareto frontier visualization in the search for preferable water quality strategies”, Environmental Modelling and Software, 20:2 (2005), 243–260 | DOI | MR

[33] Lotov A. B., Pospelov A. I., “Metod kvazirazumnykh tselei dlya tselochislennykh zadach mnogokriterialnoi optimizatsii”, Dokl. RAN, 414:3 (2007), 317–319 | MR | Zbl