Content area
Full Text
J Optim Theory Appl (2008) 138: 375396 DOI 10.1007/s10957-008-9394-2
Improved -Constraint Method for Multiobjective Programming
M. Ehrgott S. Ruzika
Published online: 18 April 2008 Springer Science+Business Media, LLC 2008
Abstract In this paper, we revisit one of the most important scalarization techniques used in multiobjective programming, the -constraint method. We summarize the method and point out some weaknesses, namely the lack of easy-to-check conditions for properly efcient solutions and the inexibility of the constraints. We present two modications that address these weaknesses by rst including slack variables in the formulation and second elasticizing the constraints and including surplus variables. We prove results on (weakly, properly) efcient solutions. The improved -constraint method that we propose combines both modications.
Keywords Multiobjective programming Scalarization -Constraint method Properly efcient solutions
Communicated by H.P. Benson.
The research of M. Ehrgott was partially supported by University of Auckland Grant 3602178/9275 and by Deutsche Forschungsgemeinschaft Grant Ka 477/27-1.
The research of S. Ruzika was partially supported by Deutsche Forschungsgemeinschaft Grant HA 1795/7-2.
The authors thank the anonymous referees, whose comments helped improving the presentation of the paper including a shorter proof of Theorem 3.1.
M. Ehrgott ( )
Department of Engineering Science, University of Auckland, Auckland, New Zealand e-mail: mailto:[email protected]
Web End [email protected]
M. EhrgottCNRS Laboratoire dInformatique de Nantes Atlantique, Universit de Nantes, Nantes, France
S. RuzikaFachbereich Mathematik, Technische Universitt Kaiserslautern, Kaiserslautern, Germany
376 J Optim Theory Appl (2008) 138: 375396
1 Introduction
Multiobjective programming is a part of mathematical programming dealing with decision problems characterized by multiple and conicting objective functions that are to be optimized over a feasible set of decisions. Such problems, referred to as multiobjective programs (MOPs), are commonly encountered in many areas of human activity including engineering, management, and others.
More precisely, let Rn and Rp be Euclidean vector spaces referred to as the decision space and the objective space. Let X Rn be a non-empty feasible set and let f be a vector-valued objective function f : Rn Rp composed of p real-valued objective functions, f = (f1,...,fp), where fk : Rn R for k = 1,...,p. A multiobjective program (MOP) is given by
(MOP) min[braceleftbig](f1(x), . . . , fp(x)) : x X[bracerightbig].
We usually assume that the set X is given implicitly in the...