A combined constraint-space, objective-space approach for determining high-dimensional maximal efficient faces of multiple objective linear programs

Abstract

Characterizations for efficient faces and certain maximal efficient faces of the objective set Y of a linear k-objective minimization problem are presented. These characterizations are used to develop an algorithm for etermining high-dimensional maximal efficient faces of Y. The algorithm requires as input an irredundant system of linear inequalities representing the efficiency equivalent polyhedron Y :=Y + R+k. A procedure for obtaining such a representation for Y has previously appeared in the literature and is included herein in order to make the paper self-contained. This latter procedure requires, in part, the generation of the efficient extreme points and efficient extreme rays of the constraint polyhedron. Hence, the overall method proposed herein can be viewed as a combined constraint-space, objective-space algorithm. The algorithm is complete for problems with 2 and 3 objectives. An illustrative numerical example is included.