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


multiple objective optimization, combinatorial optimization, complexity of computation


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.


M. Ehrgott, Multicriteria Optimization, Springer-Verlag, 2000.

M. Ehrgott, X. Gandibleux, A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization, OR Spektrum, Vol. 22, pp. 425-46 2000.

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.

H.W. Hamacher, G. Ruhe, On Spanning Tree Problems with Multiple Objectives, Ann. Oper. Res., Vol. 52, pp. 209-230, 1994.

I.V. Sergienko, V.A. Perepelitsa, Finding the Set of Alternatives in Discrete Multicriterion Problems, Cybernetics Vol. 23, pp. 673-683, 1987.

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.

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.

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.

M. Vujoševic, M. Stanojevi’c, A Bicriterion Steiner Tree Problem on Graph", Yugosl. J. Oper. Res., Vol. 13, pp. 25-33, 2003.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.