Approaches for multiobjective combinatorial optimization problems

Download

index.pdf

Date

2008

Author

Özpeynirci, Nail Özgür

Metadata

Show full item record

Item Usage Stats

185
views

99
downloads

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.

URI

http://etd.lib.metu.edu.tr/upload/2/12609216/index.pdf
https://hdl.handle.net/11511/17484

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Approaches for multi-objective combinatorial optimization problems Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2007) In this thesis, we develop two exact algorithms and a heuristic procedure for Multiobjective Combinatorial Optimization Problems (MOCO). Our exact algorithms guarantee to generate all nondominated solutions of any MOCO problem. We test the performance of the algorithms on randomly generated problems including the Multiobjective Knapsack Problem, Multi-objective Shortest Path Problem and Multi-objective Spanning Tree Problem. Although we showed the algorithms work much better than the previous ones, we also ...
Effective optimization with weighted automata on decomposable trees Ravve, E. V.; Volkovich, Z.; Weber, Gerhard Wilhelm (Informa UK Limited, 2014-01-02) In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effec...
An evolutionary algorithm for multiple criteria problems Soylu, Banu; Köksalan, Murat; Department of Industrial Engineering (2007) In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights accordin...
Solutions of large integral-equation problems with preconditioned MLFMA Ergül, Özgür Salih; Unal, Alper; Gurel, Levent (2007-10-12) We report the solution of the largest integral-equation problems in computational electromagnetics. We consider matrix equations obtained from the discretization of the integral-equation formulations that are solved iteratively by employing parallel multilevel fast multipole algorithm (MLFMA). With the efficient parallelization of MLFMA, scattering and radiation problems with millions of unknowns are easily solved on relatively inexpensive computational platforms. For the iterative solutions of the matrix e...
A stochastic programming approach to multicriteria portfolio optimization Sakar, Ceren Tuncer; Köksalan, Mustafa Murat (2013-10-01) We study a stochastic programming approach to multicriteria multi-period portfolio optimization problem. We use a Single Index Model to estimate the returns of stocks from a market-representative index and a random walk model to generate scenarios on the possible values of the index return. We consider expected return, Conditional Value at Risk and liquidity as our criteria. With stocks from Istanbul Stock Exchange, we make computational studies for the two and three-criteria cases. We demonstrate the trade...

Citation Formats

N. Ö. Özpeynirci, “Approaches for multiobjective combinatorial optimization problems,” Ph.D. - Doctoral Program, Middle East Technical University, 2008.