Approximating the Nondominated Set of R+ convex Bodies

  • The goal of a multicriteria program is to explore different possibilities and their respective compromises which adequately represent the nondominated set. An exact description will in most cases fail because the number of efficient solutions is either too large or even infinite. We approximate the nondominated by computing a finite collection of nondominated points. Different ideas have been applied, including nonnegative weighted scalarization, Tchebycheff weighted scalarization, block norms and epsilon-constraints. Block norms are the building blocks for the inner and outer approximation algorithms proposed by Klamroth. We review these algorithms and propose three different variants. However, block norm based algorithms require to solve a sequence of subproblems, the number of subproblems becomes relatively high for six criteria and even intractable for real applications with nine criteria. Thus, we use bilevel linear programming to derive an approximation algorithm. We finally analyze and compare the approximation quality, running time and numerical convergence of the proposed methods.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jorge Ivan Serna
URN (permanent link):urn:nbn:de:hbz:386-kluedo-16051
Document Type:Master's Thesis
Language of publication:English
Year of Completion:2008
Year of Publication:2008
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $