Converging preferred regions in multi-objective combinatorial optimization problems

Download
index.pdf
2011
Lokman, Banu
Show full item record
220
views
138
downloads
Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting with a decision maker (DM), the heuristic algorithm first approximately identifies the region that is of interest to the DM. Then, the exact algorithm is employed to generate all true nondominated points in this region. We conduct experiments on Multi-objective Assignment Problems (MOAP), Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path (MOSP) Problems; and the algorithms work well. Finding the worst possible value for each criterion among the set of efficient solutions has important uses in multi-criteria problems since the proper scaling of each criterion is required by many approaches. Such points are called nadir points. v It is not straightforward to find the nadir points, especially for large problems with more than two criteria. We develop an exact algorithm to find the nadir values for multi-objective integer programming problems. We also find bounds with performance guarantees. We demonstrate that our algorithms work well in our experiments on MOAP, MOKP and MOSP problems. Assuming that the DM's preferences are consistent with a quasiconcave value function, we develop an interactive exact algorithm to solve MIP problems. Based on the convex cones derived from pairwise comparisons of the DM, we generate constraints to prevent points in the implied inferior regions. We guarantee finding the most preferred point and our computational experiments on MOAP, MOKP and MOSP problems show that a reasonable number of pairwise comparisons are required.
Combinatorial optimization., Mathematical optimization.
http://etd.lib.metu.edu.tr/upload/12613379/index.pdf
https://hdl.handle.net/11511/20606
Graduate School of Natural and Applied Sciences, Thesis

Suggestions

A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture
Aksan, Yağmur; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2016)
The quadratic assignment problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems with its several real life applications. Layout design, scheduling, and assigning gates to planes at an airport are some of the interesting applications of the QAP. In this thesis, we improve the talents of a recent local search heuristic Breakout Local Search Algorithm (BLS) by using adapted Levenshtein Distance metric for similarity checking of the previously explored permutations of the QAP p...
Derivative free algorithms for large scale non-smooth optimization and their applications
Tor, Ali Hakan; Karasözen, Bülent; Department of Mathematics (2013)
In this thesis, various numerical methods are developed to solve nonsmooth and in particular, nonconvex optimization problems. More specifically, three numerical algorithms are developed for solving nonsmooth convex optimization problems and one algorithm is proposed to solve nonsmooth nonconvex optimization problems. In general, main differences between algorithms of smooth optimization are in the calculation of search directions, line searches for finding step-sizes and stopping criteria. However, in nonsmoo...
Approximating the Nondominated Frontiers of Multi-Objective Combinatorial Optimization Problems
Koksalan, Murat; Lokman, Banu (2009-03-01)
Finding, all nondominated vectors for multi-objective combinatorial optimization (MOCO) problems is computationally very hard in general. We approximate the nondominated Frontiers of MOCO problems by fitting smooth hypersurfaces. For a given problem, we lit the hypersurface using a single nondominated reference vector. We experiment with different types of MOCO problems and demonstrate that in all cases the fitted hypersurfaces approximate all nondominated vectors well. We discuss that such an approximation...
Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem
Beyaz, Muhammed; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2015)
2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Objects with di erent width and length sizes are packed in order to minimize the number of unit-capacity bins according to an objective function. Single or multiobjective versions of this well-known industrial engineering problem can be faced frequently in real life situations. There have been several heuristics proposed for the solution of 2DBPP until now where it is not possible to find the exact solutions for large problem i...
Optimization of non-uniform planar array geometry for direction of arrival estimation
Birinci, Toygar; Tanık, Yalçın; Department of Electrical and Electronics Engineering (2006)
In this work, a novel method is proposed to optimize the array geometry for DOA estimation. The method is based on minimization of fine error variances with the constraint that the gross error probability is below a certain threshold. For this purpose, a metric function that reflects the gross and fine error characteristics of the array is offered. Theoretical analyses show that the minimization of this metric function leads to small DOA estimation error variance and small gross error probability. Analyses ...
Citation Formats
B. Lokman, “Converging preferred regions in multi-objective combinatorial optimization problems,” Ph.D. - Doctoral Program, Middle East Technical University, 2011.
METU IIS - Integrated Information Service open@metu.edu.tr