A representation of the set of feasible objectives in multiple objective linear programs

AbstractMost of the analysis and algorithms for multiple objective linear programming have focused on the feasible decision set rather than the set of feasible objective values. Further, previous research in analyzing the set of feasible objective values has focused only on the optimality aspects. In this work an explicit representation of the set of feasible objective values in the form of linear inequalities is developed. Furthermore, we develop a representation for a polyhedron in the objective space which has the same maximal (Pareto efficient) structure as that of the set of feasible objective values and, moreover, is such that all of the extreme points of this polyhedron are maximal (Pareto efficient) points. This latter polyhedron provides a new approach for the analysis of large multiple objective linear programs