Authors: Stanojević, Milan
Vujošević, Mirko
Stanojević, Bogdana 
Title: Computation results of finding all efficient points in multiobjective combinatorial optimization
Journal: International Journal of Computers, Communications and Control
Volume: 3
Issue: 4
First page: 374
Last page: 383
Issue Date: 1-Jan-2008
Rank: M50
ISSN: 1841-9836
DOI: 10.15837/ijccc.2008.4.2405
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.
Keywords: Combinatorial optimization | Complexity of computation | Multiple objective optimization
Publisher: Agora University

Show full item record


checked on Jun 20, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.