Approaches for Multiobjective Combinatorial Optimization Problems

MCDM Doctoral Dissertation Award Winner, June 2011.

ABSTRACT

In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible.

We next consider generating extreme supported nondominated points of multiobjective integer programming problems for any number of objective functions. We develop two algorithms for this purpose. The first one is an exact algorithm and finds all such points. The second algorithm finds only a subset of extreme supported nondominated points providing a worst case approximation for the remaining points.

Keywords: Multiobjective Combinatorial Optimization, Traveling Salesperson Problem, Bottleneck Traveling Salesperson Problem, Computational Complexity, Extreme Points, Approximation Algorithm.

Çok Amaçlı Kombinatoryal Optimizasyon Problemleri İçin Yaklaşımlar

ÖZ

Bu tezde, çok amaçlı kombinatoryal optimizasyon problemleri üzerinde çalıştık. Çalışmamızı iki ana başlıkta gruplayabiliriz. İlk başlık, gezgin satıcı probleminin ve darboğaz gezgin satıcı problemlerinin polinom çözülebilen durumlarıyla ilgilidir. Biz bu problemlerin, farklı amaç fonksiyonlarının birleşkeleri olan çok amaçlı türevlerini ele aldık, hesaplama karmaşıklıklarını analiz ettik ve mümkün olan durumlarda kesin yordamlar geliştirdik.

İkinci başlığımız, herhangi sayıda amaç fonksiyonu olan çok amaçlı tam sayılı programlama problemlerinin destekli uç etkin noktalarını bulmakla ilgidir. Bu başlık altında iki yordam geliştirdik. İlki bu noktaların hepsini bulan bir kesin yordamdır. İkinci yordam ise bu noktaların bir alt kümesini bulmakta ancak kalan noktalar için bir en kötü durum bilgisi sunmaktadır.

Anahtar Kelimeler: Çok Amaçlı Kombinatoryal Optimizasyon, Gezgin Satıcı Problemi, Darboğaz Gezgin Satıcı Problemi, Hesaplama Karmaşıklığı, Uç Noktalar, Yaklaşıklama Yordamı.

Publications

Özpeynirci Özgür, Köksalan Murat, “An Exact Algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer Problems”, Management Science, 56 (12), 2302-2315, 2010

Abstract: In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematicway. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm's performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives.

Keywords: Multiobjective Optimization, Nondominated Points, Exact Algorithm.

Özpeynirci Özgür, Köksalan Murat, “Pyramidal Tours and Multiple Objectives”, Journal of Global Optimization, 48 (4) ,569-582, 2010.

Abstract: In this study, we work on the traveling salesperson problems and bottleneck traveling salesperson problems that have special matrix structures and lead to polynomially solvable cases. We extend the problems to multiple objectives and investigate the properties of the nondominated points. We develop a pseudo-polynomial time algorithm to find a nondominated point for any number of objectives. Finally, we propose an approach to generate all nondominated points for the biobjective case.

Keywords:  Pyramidal Tour, Polynomially Solvable, Multiple Objectives, TSP, BTSP.

Özpeynirci Özgür, Köksalan Murat, “Multiobjective Traveling Salesperson Problem on Halin Graphs”, European Journal of Operational Research, 196 (1), 155-161, 2009.

Abstract: In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.

Keywords: Traveling Salesperson Problem, Bottleneck Traveling Salesperson Problem, Multiple Objectives, Solvable Cases, Halin Graphs, Computational Complexity.