Approximating the Nondominated Frontiers of Multi-Objective Combinatorial Optimization Problems

Date

2009-03-01

Author

Koksalan, Murat
Lokman, Banu

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

246
views

0
downloads

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 is useful to find the neighborhood of preferred regions of the nondominated vectors with very little computational effort. Further computational effort can then be spent in the identified region to find the actual nondominated vectors the decision maker will prefer. (C) 2009 Wiley Periodical, Inc. Naval Research Logistics 56: 191-198, 2009

Subject Keywords

Multi-objective combinatorial optimization, Nondominated vectors, Surface fitting

URI

https://hdl.handle.net/11511/32655

Journal

NAVAL RESEARCH LOGISTICS

DOI

https://doi.org/10.1002/nav.20336

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

Converging preferred regions in multi-objective combinatorial optimization problems Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2011) 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 w...
Approaches for special multiobjective combinatorial optimization problems with side constraints Akın, Banu; Köksalan, Murat; Department of Industrial Engineering (2012) We propose a generic algorithm based on branch-and-bound to generate all efficient solutions of multiobjective combinatorial optimization (MOCO) problems. We present an algorithm specific to multiobjective 0-1 Knapsack Problem based on the generic algorithm. We test the performance of our algorithm on randomly generated sample problems against IBM ILOG CPLEX and we obtain better performance using a problem specific algorithm. We develop a heuristic algorithm by incorporating memory limitations at the expens...
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...
Identifying preferred solutions in multiobjective combinatorial optimization problems Lokman, Banu (2019-01-01) We develop an evolutionary algorithm for multiobjective combinatorial optimization problems. The algorithm aims at converging the preferred solutions of a decision-maker. We test the performance of the algorithm on the multiobjective knapsack and multiobjective spanning tree problems. We generate the true nondominated solutions using an exact algorithm and compare the results with those of the evolutionary algorithm. We observe that the evolutionary algorithm works well in approximating the solutions in the...
Finding all nondominated points of multi-objective integer programs LOKMAN, BANU; Köksalan, Mustafa Murat (2013-10-01) We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find a...

Citation Formats

M. Koksalan and B. Lokman, “Approximating the Nondominated Frontiers of Multi-Objective Combinatorial Optimization Problems,” NAVAL RESEARCH LOGISTICS, pp. 191–198, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32655.