Number of efficient points in some multiobjective combinatorial optimization problems

Abstract

The number of efficient points in criteria space of multiple objective combinatorial optimization problems is considered in this paper. The number of Pareto optimal solutions grows exponentially with the problem size. In this paper it is concluded that under certain assumptions, which are reasonable and applicable in the majority of practical problems, the number of efficient points grows polynomially. 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 even much lower than the polynomial upper bound.