Computation Results of Finding All Efficient Points in Multiobjective Combinatorial Optimization

  • Milan Stanojevic University of Belgrade Faculty of Organizational Sciences 154 Jove Ili´ca, 11000 Belgrade, Serbia
  • Mirko Vujoševic University of Belgrade Faculty of Organizational Sciences 154 Jove Ili´ca, 11000 Belgrade, Serbia
  • Bogdana Stanojevic Transilvania University of Bra¸sov Department of Computer Science 50 Iuliu Maniu, Bra¸sov, Romania

Abstract

The number of efficient points in criteria space of multiple objective combinatorial optimization problems is considered in this paper. It is concluded that under certain assumptions, that number grows polynomially although the number of Pareto optimal solutions grows exponentially with the problem size. In order to perform experiments, an original algorithm for obtaining all efficient points was formulated and implemented for three classical multiobjective combinatorial optimization problems. Experimental results with the shortest path problem, the Steiner tree problem on graphs and the traveling salesman problem show that the number of efficient points is much lower than a polynomial upper bound.

References

[1] M. Ehrgott, Multicriteria Optimization, Springer-Verlag, 2000.
http://dx.doi.org/10.1007/978-3-662-22199-0

[2] M. Ehrgott, X. Gandibleux, A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization, OR Spektrum, Vol. 22, pp. 425-46 2000.
http://dx.doi.org/10.1007/s002910000046

[3] V.A. Emelichev, V.A. Perepelitsa, On Cardinality of the Set of Alternatives in Discrete Manycriterion Problems, Discrete Math. Appl. Vol. 2, pp. 461-471, 1992.
http://dx.doi.org/10.1515/dma.1992.2.5.461

[4] H.W. Hamacher, G. Ruhe, On Spanning Tree Problems with Multiple Objectives, Ann. Oper. Res., Vol. 52, pp. 209-230, 1994.
http://dx.doi.org/10.1007/BF02032304

[5] I.V. Sergienko, V.A. Perepelitsa, Finding the Set of Alternatives in Discrete Multicriterion Problems, Cybernetics Vol. 23, pp. 673-683, 1987.
http://dx.doi.org/10.1007/BF01074927

[6] M. Stanojevic, M. Vujosevic, B. Stanojevic, Number of Efficient Points in Some Multiobjective Combinatorial Optimization Problems, International Journal of Computers, Communications & Control, Vol.III (supl. issue), pp. 497-502, 2008.

[7] M. Visée, J. Teghem, M. Pirlot, E.L. Ulungu, Two-phases Method and Branch and Bound Procedures to Solve the Bi-objective Knapsack Problem, J. Glob. Optim., Vol. 12, pp. 139-155, 1998.
http://dx.doi.org/10.1023/A:1008258310679

[8] M. Vujoševic, M. Stanojevi’c, Multiobjective Traveling Salesman Problem and a Fuzzy Set Approach to Solving It. In: D. Ivanchev, M.D. Todorov (eds), Applications of Mathematics in Engeneering and Economics, Heron Press, Sofia, pp. 111-118, 2002.

[9] M. Vujoševic, M. Stanojevi’c, A Bicriterion Steiner Tree Problem on Graph", Yugosl. J. Oper. Res., Vol. 13, pp. 25-33, 2003.
http://dx.doi.org/10.2298/YJOR0301025V
Published
2008-12-01
How to Cite
STANOJEVIC, Milan; VUJOŠEVIC, Mirko; STANOJEVIC, Bogdana. Computation Results of Finding All Efficient Points in Multiobjective Combinatorial Optimization. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 3, n. 4, p. 374-383, dec. 2008. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2405>. Date accessed: 26 sep. 2020. doi: https://doi.org/10.15837/ijccc.2008.4.2405.

Keywords

multiple objective optimization, combinatorial optimization, complexity of computation