Approaches for special multiobjective combinatorial optimization problems with side constraints

Download

index.pdf

Date

2012

Author

Akın, Banu

Metadata

Show full item record

Item Usage Stats

140
views

38
downloads

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 expense of solution quality to overcome memory issues of the exact algorithm.

Subject Keywords

Combinatorial optimization., Heuristic algorithms., Knapsack problem (Mathematics).

URI

http://etd.lib.metu.edu.tr/upload/12614603/index.pdf
https://hdl.handle.net/11511/21803

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 ...
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 multilevel optimization methods Pekmen, Bengisen; Karasözen, Bülent; Department of Scientific Computing (2009) Derivative free optimization algorithms are implementations of trust region based derivative-free methods using multivariate polynomial interpolation. These are designed to minimize smooth functions whose derivatives are not available or costly to compute. The trust region based multilevel optimization algorithms for solving large scale unconstrained optimization problems resulting by discretization of partial differential equations (PDEs), make use of different discretization levels to reduce the computati...
A modified algorithm for peer-to-peer security Akleylek, Sedat; Emmungil, Levent; NURİYEV, URFAT (2007-01-01) In this paper we present the steganographic approach to peer-to-peer systems with a modified algorithm. This gives the user a very high level of protection against being compelled to disclose its contents. Even the realization of the quantum computer cannot solve NP-hard problem in a polynomial time, a modified algorithm with steganographic use depending on Knapsack problem may make peer-to-peer systems secure.
An interactive approach for biobjective integer programs under quasiconvex preference functions Ozturk, Diclehan Tezcaner; Köksalan, Mustafa Murat (2016-09-01) We develop an interactive algorithm for biobjective integer programs that finds the most preferred solution of a decision maker whose preferences are consistent with a quasiconvex preference function to be minimized. During the algorithm, preference information is elicited from the decision maker. Based on this preference information and the properties of the underlying quasiconvex preference function, the algorithm reduces the search region and converges to the most preferred solution progressively. Findin...

Citation Formats

B. Akın, “Approaches for special multiobjective combinatorial optimization problems with side constraints,” M.S. - Master of Science, Middle East Technical University, 2012.