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

Authors Marco Laumanns, Lothar Thiele, Eckart Zitzler



PDF
Thumbnail PDF

File

DagSemProc.04461.6.pdf
  • Filesize: 360 kB
  • 11 pages

Document Identifiers

Author Details

Marco Laumanns
Lothar Thiele
Eckart Zitzler

Cite AsGet BibTex

Marco Laumanns, Lothar Thiele, and Eckart Zitzler. An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method. In Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, Volume 4461, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.04461.6

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.
Keywords
  • Multiple objective optimization
  • non-dominated set
  • Pareto set
  • epsilon-constraint method
  • generating methods

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail