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...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computers, communications & control communications & control, 2008-12, Vol.3 (4), p.374
Main Authors: Stanojevic, Milan, Vujoševic, Mirko, Stanojevic, Bogdana
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Graphs
Multiple objective analysis
Optimization
Polynomials
Shortest-path problems
Traveling salesman problem
Upper bounds
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1841-9836
1841-9844
DOI:10.15837/ijccc.2008.4.2405