Faces of a Polyhedron Katta G. Murty Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109, U.S.A. Revised July 1984 Research partially supported by NSF Grant No. ECS-8401081 1

ABSTRACT: We survey some results on faces of a convex polyhedron incident at a degenerate extreme point. We discuss applications of these to the problem of enumerating the efficient faces in a multi-objective linear program. KEY WORDS: Faces incident at a nondegenerate or degenerate extreme point, dimension of a face, canonical tableau oriented enumeration, type 1 subsets, efficient faces in a multiobjective linear program. 1. INTRODUCTION Let K be the set of feasible solutions of Ax = b (1) x 0 where A is a given matrix of order m x n and rank m. The dimension of K is c n - m. Let x be a given extreme point of K. Define P(x) = {j: j i O) Z(x) = {j: Xj = 0} The extreme point x is a nondegenerate extreme point of K if the cardinality of P(x), IP(x)l = m; a degenerate extreme point if P(x) |<m.- See Dantzig's book [2]. A hyperplane H = (x: cx = a } where c is a row vector in Rn, c $ 0, is said to have K on one of its sides if either cx2 a for all x K, or cx c a for al 1 x G K. The hyperplane H is cal led a supporting hyperplane for K if H has K on one of its sides and H n K +. A 2

face of K is either the empty set 0, or K itself, or the intersection of K with a supporting hyperplane. A well known result (see [9]) states that every nonempty face of K is the set of feasible solutions of a system of the following form for some J C { 1,..., n } Ax = b x = 0 for all j & J 2O for all j E J Extreme points of K are faces of dimension zero, edges of K are faces of dimension one, etc. In Figure 1, x is the top vertex of a pyramid 3 K in R. x is an extreme point of K. The edges el, e2, e3, e4 of K contain x. The boundary triangular regions ele2e7, ele4e6, e4e3e5, e3e2e8 are the four two-dimensional faces of K containing x. The only other face of K containing x is K itself. Figure 1. 3

An important mathematical problem encountered in optimization studies is that of enumerating the faces of K containing a specified extreme point of K. We show that the simplex canonical tableau oriented approaches (which are based on the canonical form tableau representations of the extreme point x as a basic feasible solution) may fail to generate all the faces of K containing x when x is a degenerate extreme point. We define subsets of Z(x) called type 1 subsets, and show that faces of all dimensions incident to a degenerate extreme point can be generated and are uniquely identified with maximal type 1 subsets. A well studied problem in multiobjective linear programming is to identify all maximal efficient faces. For example, in [4] J. G. Ecker, N. S. Hegner and I. A. Kouada show how this can be done in the nondegenerate case. In particular, each maximal efficient face of dimension d incident to a nondegenerate efficient extreme point x is identified with a unique set of d nonbasic variables in a canonical form that can be increased from their zero value in x. In [4, P. 356] the following statement is made about this canonical tableau oriented procedure "to handle a degenerate problem, all that is necessary is the introduction of a tie-breaking rule for the choice of the pivot row". This is false; our examples show that in the degenerate case, this canonical tableau oriented enumeration may miss some efficient faces even if all canonical form representations of a degenerate extreme point are considered. As an application of our results, we show how all efficient faces incident at a degenerate efficient extreme point x can be enumerated using the concept of type 1 subsets of Z(x). 4

2. NOTATION AND PRELIMINARIES If S, T are two sets S \ T denotes the set of elements of S not in T and I S - cardinality of S. I is the unit matrix of order m. For p f m, we denote the unit matrix of order p by Ip. If G is any matrix, define G j = the jth column vector of the matrix G th Gi = the i row vector of the matrix G In (1), the column vector A j is associated with the variable xj, j = 1 to n. A basic vector for (1) is a vector xB of m of the variables x,..., xn in (1), such that the set of column vectors A j corresponding to them is a linearly independent set. When considering the basic vector xB, variables in it are called basic variables, variables not in it are called nonbasic variables, and the square matrix B of order m consisting of columns of A associated with the basic variables in the order they are listed in xB is called the corresponding basis. The basic solution of (1) corresponding to the basic vector xB and basis B is defined by all nonbasic variables = 0 XB = B-lb = The basic vector xB, and the basis B are said to be feasible if 6' 0, infeasible otherwise. When xB is feasible the basic solution corresponding to it is called a basic feasible solution (BFS) for (1). Given the fasible basic vector xB, and the associated basis B, define B = {j: xj is a basic variable in xB } I = { 1,...,}n \B. (B,N) is the partition of { 1,..., n } into basic and nonbasic parts 5

corresponding to xB. Rearranging the columns of A into basic and nonbasic parts, A will become (B,N) where N is the m x (n-m) submatrix of A consisting of nonbasic columns. Let xN denote the vector of nonbasic variables. Rearranging the variables in (1), it can be written as XB XN B N b. XB, XN 0. The canonical tableau (or canonical form) of (1) corresponding to the fasible basic vector xB is (where N = B-1N, B = B-lb) XB xN I RN XBE, XN 0 The BFS corresponding to this canonical form is given by (xB = b, XN = 0). It is well known (see Dantzig's book [2, p. 154]) that every extreme point of K is a BFS and vice-versa. If x is a nondegenerate extreme point, it can be represented as a BFS in a canonical tableau form in a unique manner, this corrsponds to the basic vector (xj: j G P(x)). If x is a degenerate extreme point, there may be several basic vectors of (1) corresponding to it, each of them cot:ai all the variables xj for j E P(x) as basic variables. EXAMPLE 1 (I am thankful to J. G. Ecker for providing this example during the refereeing process): The convex polyhedron is the pyramid in R3 in Figure 1, defined by {x: x R3 0and x l x3 x2 - x3. xl + x3, 2 +x 3 I }. Introducing the slack variables x4 to x7, the constraint system 6

becomes x1 x2 X3 x4 X5 x6 X7 1 0 -1 -1 0 0 0 O 0 1 -1 0 -1 0 0 O 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 1 I f n....11 I -v I I' A -11 -j v J ror all j. Consider the top vertex of the pyramid x = (1/2, 1/2, (x1, x2, x3, x7) is a basic vector associated with x. to the basic, nonbasic partition (B = {1, 2, 3, 7}, N The canonical tableau corresponding to it is 1/2, 0, 0, 0, o) It corresponds = {4, 5, 6} ). Canonical form xl x2 x3 X4 basic variable X5 x6 X7 X1 X2 x3 x7 1 0 0 0 O 0 1 0 0 sO 0 -1/2 0 1/2 1 1/2 0 -1 0 -1 0 1 1/2 1/2 1/2 -1 0 1/2 0 1/2 0 1/2 1 0 x is a degenerate extreme point, and the basic vectors (x1, x2, x3, x4), (xl, x2, x3, x5), (xl, x2, x3, x6) are also associated with x. Hence in this case, the degnerate extreme point x has four different canonical form representations. 3. FACES INCIDENT AT A NONDEGENERATE EXTREME POINT Let x be a nondegenerate extreme point of K. Let xB = (xj:j G P(x)) be the basic vector of (1) corresponding to x. 7

This basic vector corresponds to the basic, nonbasic partition (B = P(x), N = Z(x)) for (1). We have the following results. (i) The dimension of K is n - m (a sufficient condition for the dimension of K to be n - m is that (1) have a nondegenerate extreme point, see [6, 9]). (ii) Each nonbasic variable xj, j ~ N enters xB with a strictly positive value, generating an edge of K containing x; conversely all edges of K containing x are obtained this way. See Dantzig's book [2, p. 155]. (iii) Each subset J c N, i J = r, determines a unique rdimensional face of K containing x, F(x,J) = {x: x r K, xj = 0 for all j E N\J } Conversely every r-dimensional face of K containing x is obtained this way. The set F(x,J) can be viewed as the face obtained when the nonbasic variables xj for j ( J are allowed to increase from their current level of zero in x in the basic, nonbasic partition (B,N). (iv) If K has a nondegenerate extreme point, and a new nonnegative variable xn+l associated with a column vector A n+l is introduced into (1), it has the effect of increasing the dimension of the set of feasible solutions by 1 to n - m+l. 4. SITUATION FOR A DEGENERATE EXTREME POINT Let x be a degenerate extreme point of K and let xB be a basic vector for (1) corresponding to it, with (B,N) as the basic, nonbasic partition. The results discussed in Section 3 may not hold 8

anymore. If (1) has no nondegenerate BFS, the dimension K may be < n - m. In this case, when a new variable Xn+1 is introduced into (1), the dimension of the set of feasible solutions may remain unchanged, or may go up by 1 or more. Consider the following example. x1 X2 X3 X4 X5 x6 1 -D 1 1 1 1 0 0 1 0 0 0 0 1 x O, j = 1 to 6 Here n = 6, m = 2, x = (0, 1, 0, 0, 0, O)T is the unique feasible solution, and the dimension of the set of feasible solutions is zero. If the new nonnegative variable x7 associated with the column vector (-1, 0) is introduced into this system, the dimension of the set of feasible solutions goes up to 5. Also, in this degenerate case, if J c, J J = r, the set / x: x E K, xj = 0 for all j E N\J is of course a face of K, but its dimension may be c r, and faces obtained this way by taking different subsets J C N may not be distinct. Also, for r >1, all r-dimensional faces of K conaining x cannot be obtained by this procedure by considering only one basic, nonbasic partition corresponding to x, or even all the basic, nonbasic partitions corresponding to x one by one. 5. EDGES OF K CONTAINING A DEGENERATE EXTREME POINT Let x = (x) be a degenerate extreme point of K. For notational convenience, assume that P(x) = { 1,..., p } = P, Z() = { p+l,..., n = Z. Performing pivots on columns of xj, j G P transforms (1) into 9

Xp xZ Ip G ~p~ ~bp 0 0 D 0 ii i iii Consider the homogeneous system Dxz = 0 D2~~~~z = 0 ~~(2) XZ Every basic vector xB for (1) corresponding to x is of the form (xj: j E P U Q) where Q c Z, Q = m-p, and (xj: j: Q) is itself a basic vector for (2); thus Q corresponds to a square nonsingular submatrix of D of order m - p. Let xB = (xj: j C P U Qu) u = 1 to L be all the distinct basic vectors of (1) corresponding to x. For u = 1 to L, Bu = (j: xj is a basic variable in the basic vector XgB Nu = 11,..., n } \ B = Z\Qu (Bu, Nu) is the basic, nonbasic partition corresponding to the basic vector X. Define B Su = j: j C Nu, and the updated column vector of xj in the canonical tableau of (2) with respect to the basic vector (xj: j E Qu) is } The set,Su is the index set of all nonbasic variables which enter the basic vector xB for (1) with a positive value. Thus the nonbasic variable xs, s E Nu, enters the basic vector xBg for (1) with a 10

positive value and thereby generates the edge of K, { x: x = (xj) E K, xj = 0 for all j e Nu \ {s ) containing x iff s u8. Conversely, every edge of K containing x can be obtained in this manner, and is therefore of the form given above for some u = 1 to L and s 6 8u. The same edge may appear several times in this enumeration. See [1, 9]. Example 2: Consider the three dimensional pyramid and its extreme point x discussed in Example 1. Here n = 7, m = 4 and P(x) = P = {1, 2, 3 }, Z(x) = Z = 4, 5, 6, 7. So p = 3 and m-p = 1. Choosing Q1 = {7 leads to the basic vector xB = (xl, x2, x3, x7). This corresponds to the basic, nonbasic partition (B1 = 1, 2, 3, 7}, N1 = {4, 5, 6 ). From canoncial tableau T1 we verify that only the nonbasic variables x4, x6 can enter the basic vector xBg with a positive value. Thus S1 = {4, 6 }. We get two distinct edges containing x, one by entering x4 into xB and the other by entering x6 into xB1. Other edges containing x are obtained by repeating this process with other basic, nonbasic partitions corresponding to x. On the question of determining the dimension of K, it is possible to do it from a local study at a degenerate extreme point x. The following theorem characterizes the dimension of K using the information contained in all the canonical tableaus for (1) corresponding to x. THEOREM 1: Let S = U(S: u = 1 to L). Then (i) in every point x = (xj)e K, xj = 0 for all j Z\S, (ii) dimension (K) = PU S - rank A j: jE PUS }. PROOF: From the above arguments we know that xj = 0 for each j Z \ S, on each edge of K containing x, this proves (i). After setting all such xj = 11

0,(1) reduces to (A.j xj: j P U S) = b (3) Xj o0,j E P U S For each variable in (3), there are feasible solutions of (3) in which that variable is > 0. Since (3) is feasible, the number of nonredundant equality constraints in (3) is rank {A: j E P U S } Since the smallest dimension affine space containing K is characterized by the system of equality constraints in (3) together with xj = 0 for each j E Z \ S, we conclude that the dimension of K is P U - rank { A j: j E P U S. 6. FACES OF DIMENSION ~ 2 CONTAINING x Let x be a degenerate extreme point of K. In the notation of Section 5, for u = 1 to L, each nonbasic variable xj for j E Su enters the basic vector xB with a positive value. For J C Su, define F(x,J) = { x = (xj) E K, x. = 0 for all j G Nu \ J The set F(x, J) is a face of K containing x, of dimension [J i; we can think of this face as the one obtained when the nonbasic variables xj for j 6 J are allowed to assume positive values in (1) besides those in the basic vector xB. Repeating this process with each of U. the basic vectors XB, u = 1 to L corresponding to x, other faces of K containing x can be obtained. However, this tableau oriented enumeration involving basic vectors for (1) corresponding to x one at a time, may not produce all the faces of K of dimension d containing x, for d 2. The difficulty arises because for d -2, there can be faces of K of dimension d incident at x, but there need not be d 12

nonbasic variables that can be increased from their current level of zero in x, no matter what canonical form representation of x is used. Example 3: Consider the three dimensional pyramid and its extreme point x discussed in Example 1. In each of the four possible canonical form representations of x, at most two nonbasic variables can be increased from zero, and yet the pyramid itself is a 3 dimensional face incident at x. Thus in order to enumerate all faces of K containing the degenerate extreme point x, focusing on the basic, nonbasic partitions corresponding to x would not help. Instead, we should use the index set Z(x) directly. Find S = U (Su: u = 1 to L) defined in Theorem 1. This is the set of all j e Z(x), for which a feasible point x exists in K with xj => 0. Call a subset J c S a type 1 subset if for each t G J, the optimum objective value in the following LP (5) is > O. maximize xt subject to (A.jxj: j G P U J)= b (5) x. 0 for each j E P U J By the results in Section 5, S itself is a type 1 subset. We have the following results: 1. There is a unique face of K incident at x corresponding to each type 1 subset J C S. It is 13

F(x,J) ({ x: x = (xj) E K, xj = 0 for each j e Z \ J } and the dimension of this face F(x, J) is [P(x) U J I - rank { A j: j E P(x) U J |. Conversely, every face of K incident at x is uniquely identified with a maximal type 1 subset. (The type 1 subset identified with a face of K containing x in this correspondence is the set of all j ~ Z(x) such that x. assumes a positive value in the face.) 2. If x is a nondegenerate extreme point of K (i.e., I P(x) = m), S = Z(x), and every subset J C Z(x) is a type 1 subset and the dimension of the face F(x, J) defined as in 1 above is always J. 3. If J is a type 1 subset and j E S \ J is such that J U ( j } is also a type 1 subset, then dimension of F(x, J U { j }) = 1 + dimension of F(x, J). 4. Each set A C S has a unique maximal type 1 subset. That type 1 subset of A is the set of all r E A for which the maximum value of xr over the set of feasible solutions of Z(A.jXj: j P U A ) = b Xj - 0, j P U A is 0. All type 1 subsets can be obtained by repeating this procedure with different subsets of S. 5. A proper subset of a type 1 subset may not be type 1. If JCAC S, and J is a type 1 subset, then the maximal type 1 subset of A determined as in 4 above is: J.

6. The union of any two type 1 subsets is also a type 1 subset, that is, the class of type 1 subsets associated with the extreme point i is closed under the set union operation. Example 4: Consider the degenerate extreme point x for the pyramid discussed in Examples 1, 2. The edges el, e2, e3, e4 incident at x in Figure 1 correspond to the type 1 subsets 4,7j, 6, 7}, {6, 5, j4, 53 respectively. The four 2-dimensional faces incident at x, el e2e7, e2e3e8, e3e4e5, e4ele6 correspond to the type 1 subsets ~4,6,7i, 5, 6, 7}, 44, 5, 6J, j4, 5, 7} respectively. The only other type 1 subset is 4, 5, 6, 7} which corresponds to the whole pyramid. 7. Let J1,... JM be all the type 1 subsets corresponding to edges of K incident at x. Then for any QC {1,..., M, the set U Ji is a ieQ - type 1 subset, and conversely every type 1 subset associated with x is of this form. The type 1 subset associated with any face of K containing x is the union of the type 1 subsets associated with edges of K incident at x contained in this face. 7. APPLICATION TO MULTIOBJECTIVE LINEAR PROGRAMMING Consider the problem of finding the set of all vector minima for the multiobjective LP with t objective functions C1 x,..., Ct x over

x E K. Let C be the t x n matrix with rows Ci., i = 1 to t. In this problem a point x0~ Kis a vector minimum (or an efficient point, or a pareto-optimal point or a nondominated feasible solution) if there exists no x E K satisfying Cx Cx0 (given vectors 7 = (kj), 7? (17j) of same dimension, c 7 iff j = 77 for all j and f j c 1 for at least one j). The set of all vector minima, known as the efficient frontier, is a union of some faces of K, which is a simply connected set [4, 11, 12, 10, 8, 7, 9]. A face of K is said to be an efficient face if every point in it is an efficient point. It is well known that a face of K is efficient iff a relative interior point in it is efficient [12]. Algorithms for computing all the efficient extreme points and edges using a tableau oriented approach are discussed in [3, 4, 5, 7, 8, 10, 11, 12]. These algorithms also obtain all the efficient faces of K if (1) is nondegenerate. However, when (1) is degenerate, these tableau oriented approaches may not obtain all the efficient faces. Let x be an efficient extreme point of K (degenerate or nondegenerate). Let P = P(x), Z = Z(x) as in Section 5, with P I= p. Performing pivots on columns of xj, j C P, transform (1) as in Section 5, and price out these columns in each of the objective rows, leading to the following tableau.

THEOREM 2: Let J be a type 1 subset of Z. Let Cj, Dj be respectively the submatrices consisting of columns of Cz, D corresponding to j C J. The face F(x, J) = { x: x = (x.) E K, and xj = 0 for j E Z\J ) is efficient iff the system (6) in y Rn-p fJ = ( f j: j 6 J) has no feasible solution jlr* * -Czy + CJ j: 0 Dy = 0 DJ j = 0 (6) y 0 ~j 0. 17

17-1 PROOF: The proof is similar to the proofs of results discussed in [12, 4]. Since J is a type 1 subset of Z, a point x = (x.) in the relative interior of F (x, J) satisfies x >o for j J U and x. =o for j( Z\J. If (y, ~j ) is a feasible solution of (6), we use this solution to construct a point x~ in the relative interior of the face F(x, J), and another feasible solution x K, satisfying Cx ~Cx~, which proves that x~ is not an efficient point and that F (x, J) is not an efficient face. Conversely, if F (x, J) is not an efficient face, for every x in its relative interior, there exists another point x K such that C C x, and using x, we construct a feasible solution to (6). Suppose (y, SJ ) is a feasible solution of (6). Define yO = (yO) Rn P by yq = j for j E J, 0 otherwise. Let Cp be the submatrix consisting of columns of C corresponding to j E P. Similarly, given any vector x = (xj) E 1n denote x = (xp, xz) where Xp = (xj: j P P), xz = (x: j Z). It can be verified that for all x (xp, XZ) 1K, Cx = Cpxp + CZx x0 = (p, x ) = (p - Gy, Ey~) is a relative interior point of the face F(x, J) for E positive but sufficiently small. Define x = (x, x ) = (p - EGy, y). For positive but sufficiently small, verify that x1 E K and that Cxl ' Cx, so x is not a vector minimum, and hence the face F(x, J) is not efficient. To prove the converse, suppose F(x, J) is not efficient. Since J is a type 1 subset of Z, there exists a point x = (xp, xZ) in the relative interior of the face F(x, J) satisfying x;j: 0 for j e J

and xj = 0 for j Z \J. Since the face F(i, J) is not efficient, there exists an x (xp, xZ) E K satisfying Cx _ Cx. So C zxz o CZz, that is, (y = Xz, = - xj) is feasible to (6). U Since the feasibility of (6) can be checked through standard linear programming techniques, Theorem 2 provides a method to check whether the face F(x, J) containing x is efficient for any type 1 subset J. If F(i, J) is an efficient face, it can be stored by identifying it with the index setP U J (these are the indices of the variables which take positive values in the face, all variables with indices outside this set are zero in this face). In [4] maximal efficient faces are stored by identifying them with a positive vectorX( Rt such that the face is the set of alternate optima to the LP: minimize AtCx over x ( K. Such a X can be obtained by finding a point in the relative interior of the face (if the face is F(x, J), this is a point x in the face with xj > 0 for j 6 P U J, a point like this is obtained as a byproduct of the work needed to check that the subset J is a type 1 subset) and then using duality as in [9, Theorem 17.3]. To generate the efficient frontier, start with an efficient extreme point x obtained by the methods discussed in [3, 4, 5]. Find maximal type 1 sets J satisfying the conditions in Theorem 2; for each such J, F(x, J) is an efficient face containing x, put them in a list. Now the efficient extreme point x is explored. Select an adjacent or extreme point x which is not yet explored, on one of the efficient A faces containing x, and repeat the process with it. The method terminates when every extreme point on each of the efficient faces generated has been explored. At that stage, the list contains all the efficient faces of K. If this enumeration encounters a degenerate extreme point of K, since the type 1 subsets associated with that

extreme point have to be examined, the problem of determining all the efficient faces containing that degenerate extreme point may be a prohibitive job as pointed out in [12]. 8. FACES OF POLYHEDRA DESCRIBED BY GENERAL LINEAR SYSTEMS Let r be the set of feasible solutions of the general system Ai.x = bi, i = 1 to m (7) 2 bi, i = m + 1 to m + v where the Ai. are the rows of an (m + v) x n matrix A, and { Ai. i = 1 to m} is a linearly independent set. For any x r let I(x) = i: Ai. = bi, i = 1 to m + v The feasible solution x E r is an extreme point of r (i.e., a BFS of (7)) iff rank {Ai: i E I(x)} = n. It is appropriate to define the BFS x of (7) to be nondegenerate if [ I(x) = rank (Ai.: i I(x) = n, and degenerate if I I(x) = rank {Ai: i I(x)} = n. For this general system, the following results can be verified. Suppose x is a degenerate extreme point of K. Let E = i: m+l i m+v, and Ai.x = bi for all x r}. To determine whether a particular i belongs to K, we can solve the LP: max Ai.x over x P. The dimension of r is n - rank ( A:i i l,..., m) U E} [6]. 210

To determine edges of P incident at the BFS x, identify subsets JC I(x) n { m+l,..., m + v} satisfying: (i) rank { Ai: i. I(x) \ J = n - 1, (ii) the system (8) has a solution y E Rn. Ai.Y > 0, i E J - 0, i ~ I(x) \ J (8) Because of property (i-), it can be verified that if (8) has a solution y, that solution is unique except for a positive scalar multiplier. Each such subset J defines a unique edge of r incident at x, the edge being the set of feasible solutions of Ai. x = bi, i i I(x) \ J > bi, otherwise (9) this edge is also x: x = x + Xy, 0 } where y is a solution of (8) and X is the maximum value of X that keeps A. (x + Xy) - bi - for all i {m+l,..., m+v}\I(x) (this can be determined by the usual minimum ratio formula). If x is a nondegenerate BFS of (7), dimension (P) = n - m, and each subset J of I(x) n {m+l,..., m+v ) of cardinality 1 satisfies (i), (ii) and thus generates an edge of r incident at x; hence x lies on exactly n - m edges of r. 2 -

Again let x be an extreme point of. Let J C I(x) n { m+l,..., m+v satisfying: (iii) rank { Ai: i E I(x) \ J} is n - r (iv) the system (10) has a solution y ~ Rn Ai.Y 0 for i 6 J = 0 for i ~ I(x) \ J (10) Then there is an r-dimensional face of P containing x associated with J, it is the set of feasible solutions of Ai x = bi, i E I(x) \ J > bi otherwise and every r-dimensional face of P containing x is obtained this way. It can be verified that if x is a nondegenerate extreme point of r, every subset J c I(x) n m+l,..., m+v } with J = r satisfies (iii), (iv) and thus generates an r-dimensional face of r, n-m hence P has exactly ) faces of dimension r containing a r nondegenerate extreme point. ACKNOWLEDGEMENT: I thank the two referees for their suggestions which greatly improved the presentation. 7

REFERENCES 1. C. A. Burdet, "Generating all the faces of a polyhedron", SIAM Journal on Applied Mathematics XXVI (1974) 479-489. 2. G. B. Dantzig, Linear programming and extensions, (Princeton University Press, Pinceton, N.J., 1963). 3. J. G. Ecker and N.S. Hegner, "On computing an initial efficient extreme point", Journal of the Operational Research Society 29, 10 (1978) 1005-1007. 4. J. G. Ecker, N. S. Hegner, and I. A. Kouada, "Generating all maximal efficient faces for multiple objective linear programs", Journal of Optimization Theory and Applications 30, 3 (1980) 353-381. 5. J. G. Ecker and I. A. Kouada, "Finding all efficient extreme points for multiple objective linear programs", Mathematical Programming 14 (1978) 249-261. 6. U. Eckhardt, "Theorems on the dimension of convex sets", Linear Algebra and Its Applications 12 (1975) 63-76. 7. J. P. Evans and R. E. Steuer, "A revised simplex method for linear multiple objective programs", Mathematical Programming 5, 1 (1973) 54-72. 8. H. Isermann, "The enumeration of the set of all efficient solutions to a linear vector multiple objective program" Operational Research Quarterly 28 (1977) 711-725.

9. K. G. Murty, Linear programming (Wiley, N.Y. 1983). 10. J. Philip, "Algorithms for the vector maximization problam", Mathematical Programming 2, 2 (1972) 207-229. 11. J. Philip, "Vectormaximization at a degenerate vertex", Mathematical Programming 13 (1977) 357-359. 12. P. L. Yu and M. Zeleny, "The Set of all nondominated solutions in linear cases and a multiple criteria simplex method", Journal of Mathematical Analysis and Applications 49 (1975) 430-468.