Approximating the Nondominated Frontiers of Multi-Objective Combinatorial Optimization Problems

Koksalan, Murat
Lokman, Banu
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


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: