Hide/Show Apps

Approaches for multiobjective combinatorial optimization problems

Download
2008
Özpeynirci, Nail Özgür
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.