Computation Results of Finding All Efficient Points in Multiobjective Combinatorial Optimization

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 per- form experiments, an original algorithm for obtaining all efficient points was formu- lated and implemented for three classical multiobjective combinatorial optimization problems. Experimental results with the shortest path problem, the Steiner tree prob- lem on graphs and the traveling salesman problem show that the number of efficient points is much lower than a polynomial upper bound.