License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.04461.6
URN: urn:nbn:de:0030-drops-2465
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/246/
Go to the corresponding Portal

Laumanns, Marco ; Thiele, Lothar ; Zitzler, Eckart

An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method

pdf-format:
04461.LaumannsMarco.Paper.246.pdf (0.4 MB)

Abstract

We discuss methods for generating or approximating the Pareto set of multiobjective optimization problems by solving a sequence of constrained single-objective problems.
The necessity of determining the constraint value a priori is shown to be a serious drawback of the original epsilon-constraint method. We therefore propose a new, adaptive scheme to generate appropriate constraint values during the run. A simple example problem is presented, where the running time (measured by the number of constrained single-objective sub-problems to be solved) of the original epsilon-constraint method is exponential in the problem size (number of decision variables), although the size of the Pareto set grows only linearly. We prove that --- independent of the problem or the problem size --- the time complexity of the new scheme is O(k^{m-1}), where k is the number of Pareto-optimal solutions to be found and m the number of objectives. Simulation results for the example problem as well as for different instances of the multiobjective knapsack problem demonstrate the behavior of the method, and links to reference implementations are provided.

BibTeX - Entry

@InProceedings{laumanns_et_al:DagSemProc.04461.6,
  author =	{Laumanns, Marco and Thiele, Lothar and Zitzler, Eckart},
  title =	{{An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method}},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4461},
  editor =	{J\"{u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/246},
  URN =		{urn:nbn:de:0030-drops-2465},
  doi =		{10.4230/DagSemProc.04461.6},
  annote =	{Keywords: Multiple objective optimization, non-dominated set, Pareto set, epsilon-constraint method, generating methods}
}

Keywords: Multiple objective optimization, non-dominated set, Pareto set, epsilon-constraint method, generating methods
Collection: 04461 - Practical Approaches to Multi-Objective Optimization
Issue Date: 2005
Date of publication: 10.08.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI