A REPRESENTATION OF AN EFFICIENCY EQUIVALENT POLYHEDRON FOR THE OBJECTIVE SET OF A MULTIPLE-OBJECTIVE LINEAR PROGRAM

Associated with the objective set Y of a linear k-objective minimization problem is the efficiency equivalent polyhedron (Y) over tilde = Y + R (k)(+) . Since (Y) over tilde has the same efficient structure as Y and since every extreme point of (Y) over tilde is efficient, this polyhedron provides a promising avenue for the analysis of the given multiple objective linear program (MOLP). However, in order to fully explore this avenue, a representation of (Y) over tilde as a system of linear inequalities is needed. In this paper an algorithm is given to construct a matrix H and a vector g such that (Y) over tilde has the representation Hy greater than or equal to g, and it is shown that no inequality in this representation is redundant. The input data for the algorithm are a finite set of points of Y containing the efficient extreme points and a finite set of recession directions for Y containing the directions associated with unbounded efficient edges. These data, which can be obtained using standard MOLP software packages, are used to form a polar polyhedron whose extreme points are precisely what is needed to define H and g.