EXTREME POINT ENUMERATION Katta G. Murty Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Sung-Jin Chung Department of Industrial Engineering Seoul National University Seoul, Korea Technical Report 92-21 February 1992 Revised June 1992

ll__T_1_11__7Fr____________i____i_~Hib 1 — —1 --— IX- ----T —^-IilE ---~C ---- --- ---~ —II *- I Extreme Point Enumeration Katta G. Murty* Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117, USA and Sung-Jin Chung** Department of Industrial Engineering Seoul National University Seoul, South Korea June 1992 Abstract ' We discuss an algorithm for enumerating the vertices of a convex polytope specified by a system of linear constraints. Existing algorithms for this problem are usually based on enumerating the feasible basic vectors for the system, and their worst case computational complexity is exponential in the number of vertices of the polytope. Our algorithm generates an objective coefficient vector in each iteration, such that the optimization of this objective function subject to the specified constraints by linear programming techniques leads to a new vertex; until all the vertices are obtained. When the system of constraints has n variables and size L; the worst case computational complexity of our algorihtm is O(~5n4L) where e is the unknown number of vertices of the polytope. Key words Convex polytopes, enumeration of extreme points and facets, adjacency, segments, polynomial time algorithms. *Author for correspondence. **Work carried out while on sabatical leave in the Industrial and Operations Engineering Department at the University of Michigan in Ann Arbor. 1

1 Introduction The problem of enumerating all the extreme points (or vertices) of a convex polytope specified by a system of linear constraints has been studied extensively in the literature. It is discussed in textbooks (see Section 3.19 in [14]), and a large number of journal articles have discussed a variety of algorithms for it (see [1-6, 10-11, 18]). There are some applications in which this problem appears, but the typical exponential growth of the number of extreme points in terms of the number of variables, n, and the number of constraints p in the linear system describing the polytope make this practical only for systems in which both n and p are small. In spite of this, there is considerable mathematical interest in developing algorithms for this problem which can be considered efficient from a computational complexity points of view, when this efficiency is assessed relative to the enormity of the task. This is the main issue in this paper. Without any loss of generality, we consider the polytope K which is the set of feasible solutions of the system of constraints Ax = b (1) x = 0 where A is a matrix of order m x n and rank m, and n > m. Forj = 1 to n let A.j denote the jth column vector of A, it is the column of the variable xj in (1). Our method can be extended very directly to handle polytopes defined by more general systems consisting of linear equations, inequalities and/or bounds on variables; or such general systems can be transformed into a system of the form (1) by simple linear transformations that preserve one to one correspondence between extreme points of the original and the transformed systems. We assume that A, b are integer, and that K is nonempty and bounded. If max {xj: x E K} = 0, then the variable j is equal to the constant 0 all over K and can be eliminated. So, wasse assume that max j: x K > 0 for all j = 1 to n. Thi implies that the dimension of K is n - m. unknown number of extreme points of K. All the methods discussed in the literature for enumerating the extreme points of K are based on enumerating the feasible bases for (1) (see [14]). Every extreme point of K is the basic feasible solution (BFS) associated with one or more feasible bases for (1), this is the principle used in these methods. If system (1) is nondegenerate, every extreme point of K is associated with a unique feasible basis for (1) and vice versa, and after an initial feasible basis is obtained, these methods require at most e(n - m) pivot steps on (1) before termination, an effort which grows linearly with e. However, when (1) is degenerate, there may be several feasible bases associated with an extreme point of K, the number of feasible bases may be strictly greater than e, and may even grow exponentially with e and n. An example of this can be obtained from the class of problems constructed by J. Edmonds [8] (see also [16]) to display the worst case behavior of the primal simplex algorithm on the shortest chain problem. For r - 2, the rth problem in this class is a minimum cost flow problem on the network in Figure 1 with (2r + 1) nodes and (4r - 1) arcs. The lower bound and capacity for flow on each arc are 0, oo respectively; the source, sink nodes are 2r, 2r + 1; and it is required to ship one unit from the source to the sink at minimum cost. The cost data is not given in Figure 1 since it is not relevant for our discussion. There is a unique feasible flow vector for this problem (this has a flow of one unit on the arc (2r, 2r + 1), and zero flow on all the other arcs), hence e = 1; but the system of constraints in this problem has at least 3(2w) feasible bases, all corresponding to the single feasible solution. So, when (1) is degenerate, the computational effort in the traditional methods of enumerating extreme points of K based on enumerating feasible bases for (1) is not polynomially bounded in n, L, e in the worst case. 2

Figure 1 Network for the rth problem in the class for r = 2. All lower bounds are 0, and capacities are +oo. Source = node 2r, with 1 unit available, sink = node 2r + 1 with requirement 1 unit. The motivation for this study came from the question "is there an algorithm for enumerating the extreme points of K when (1) is degenerate, with worst case computational effort bounded above by a polynomial in e, L and n?" posed by J. S. Provan [17]. Provan has answered this question in the affirmative for polyhedra associated with network linear programs. Here we answer this question in the affirmative for polytopes specified by systems of general linear constraints, by providing an algorithm. In pivotal algorithms such as the simplex algorithm, perturbation is a standard technique used to prevent the problem of cycling under degeneracy [14]. This would replace b in the right hand side of (1) by b(e) = b+ (e, e2,..., em)T, where e is not given a specific value, but treated as a small positive parameter whose value is smaller than any other positive number not involving e with which it is compared. Even if the original system (1) is degenerate, the perturbed system is nondegenerate when e is sufficiently small [14]. A feasible basis for the perturbed system is said to be a lexico feasible basis for (1). Any BFS for the perturbed system becomes a BFS for the original system (1) when e is set equal to 0 in it. Two BFSs of the perturbed system may be different when e is a small positive number, but may correspond to the same degenerate BFS of the original system obtained by setting e = 0 in them. Since the perturbed system is nondegenerate, its extreme points can be enumerated in time which grows linearly with their number, by enumerating the lexico feasible bases for (1); and then, by setting e = 0 in each of these extreme points we get a list of extreme points of the original system (1); this list may duplicate each degenerate extreme point of (1) several times because of the fact mentioned above. Unfortunately, the number of lexico feasible bases for (1), i.e., the number of extreme points of the perturbed system, could grow exponentially with the number of extreme points of the original system (1). As an example, consider the polytope K1 C IR2n+1 which is the set of feasible solutions of X1 + Z(xj+i: over 1 nj: q) +q 1, q=1 to n (2) Xj=O, q-O, for j=1 to n+l,q=1 to n discussed in [17]. The dimension of K1 is n + 1, and it has exactly n + 3 extreme points which are (0, 0, e), 3

______ —~ I (1, 0, 0); (0,1,j, Ij j), j = 1 to n, and (0, e/(n - 1), 0), where I.j is the jth column vector of the unit matrix of order n, and e E IRn is the vector of all Is. The right hand side constants vector in (2) is e. When it is perturbed into e + (en, En-,, e) T, the perturbed system has more than 2" extreme points, since there are at least 2" lexico feasible basic vectors with basic variables among x2 to xn+ and sl to Sn only. That is, the number of lexico feasible bases grows exponentially with the number of extreme points for the original system in this example. This indicates that methods based on enumerating the lexico feasible bases do not by themselves provide a solution to our problem. For any matrix H, we denote by Hi., H.j, its ith row vector and jth column vector respectively. If {a,..., at} is a set of points in IRn, we denote its convex hull by < a1,..., at >. The affine rank of {a',..., at} is defined to be the rank of the set {a2 - a1,..., at - a}, it is the dimension of the affine space of {al,...,at}. We will use the abbreviation LP for "linear program". 2 Some Preliminaries (3) (4) Min xj Max Xj over x E K over x E K If the optimum objective values in (3) and (4) are the same, = a say, then K lies on the hyperplane x3 = a in IRn. In this case fix Xj at a in (1) and eliminate it from the system. Each extreme point of the reduced system becomes an extreme point of the original system when we include xj at value a in it. So, in the sequel we assume that the maximum value of any variable in (1) is strictly greater than its minimum value. The operations carried out here do not change the dimension of the set of feasible solutions of (1), which we continue to denote by K. Let XB = (I1,..., Xm) say to be specific, be a basic vector for (1). XN = (Xm+i,...,Xn) is the nonbasic vector when considering this basic vector. Let (B, N) be the partition of A corresponding to the basic, nonbasic partition of x into (xB, xN). The equality constraints in (1) are equivalent to XB = B-b - B-1N N (5) Using these, the basic variables XB can be eliminated and system (1) expressed purely in terms of the nonbasic variables xN as -B-1NxN + B-lb 0 (6) XN = 0 In (6) all the constraints are inequality constraints, and if XN is an extreme point of the set of feasible solutions of (6), then (~B, xN) (where XB is obtained from (5) by substituting XN = xN) is an extreme point of (1), and vice versa. Thus enumerating extreme points of (1), or those of (6), are the same problem. In fact, the set of feasible solutions of (6) is K itself expressed in the space of nonbasic variables XN; in this space, K is a full dimensional convex polytope. We will find it convenient to use this transformation. 4

How to Check the Adjacency of Two Extreme Points on the Convex Hull of a Given Set of Points Consider-the distinct set of points {pl,..,pt} C IR with t 3 and s 2, and K2 < pl,..,pt > with each pk being an extreme point of K2. The following Theorem 1 provides a result that can be used to check whether two of these points, say pl and p2 are adjacent on K2. THEOREM 1 Let K2 = < pl,...,pt > C IR, where each pk is an extreme point of K2 and all the points are distinct. The points p1 and p2 are adjacent on K2 iff there exists a c = (ci,..., c8) satisfying c(pl-p2) = 0 (7) c(pl_ pk) > 0, for all k = 3 tot PROOF First assume that t 4. From [12]; p1 and p2 are adjacent on K2 iff the following system of constraints in variables al,..., at is infeasible. alp1 + a2p2 _ Ek=3ak = 0 - al + a2 = 1 (8) Ek=3 ak = 1 Eks^ = 1 ak 0, k= 1 to t By Motzkin's theorem of the alternatives, (7) has no solution c iff the following system in variables (6, 1r3 to lrt) has a solution. 6(p _p2) + Ek_37k( _ pk) = 0 (9) 6 unrestricted; (7r3 to 7rt) > 0 and:: 0 ( r3 to 7rt) > 0 and: 0 implies that in any solution to (9), Ek=3 rk > 0; then dividing both sides by this k=3 rk we get a new solution in which this sum is one. Hence (9) has a solution iff the following (10) has a solution. S(p _p2) + Ek 3 rk(l-p k) = 0 Ek=3 k = 1 (10) S unrestricted; (1r3 to lrt) > 0 We claim that in any solution to (10), 6 must be < 0. Suppose not. If (, r3,..., 7rt) is a solution of (10) with 6 > 0, then from (10) we obtain p1 = (6p2 + Ek=3 7rkp)/(6 + 1), i.e., p1 is a convex combination of p2 to pk, contradiction to the fact that pl is an extreme point of K2. So, if (10) has a solution, 6 < 0 in it. Using a similar argument it can be verified that in any solution to (10), 6 > -1. 5

Thus, if (8, T3,...,,it) is a solution of (10), then 0 < S < 1, this implies that a, = 1 + 6, ~2 = -6; (fk = Trk for k = 3 to t, is a solution for (8). Similarly, if (al,..., at) is a solution for (8), then we must have da, d2 both > 0 since p1,p2 are extreme points ofK2r and 7r, = ik for k = 3 to t, 6 = -d2 is a solution for (10). Thus (10) has a solution (6, Irk, k = 3 to t) iff (8) has a solution (ak, k = 1 to t). So, (8) has no solution (ak, k = 1 to t) iff (7) has a solution c, proving the theorem for the case t - 4. If t = 3, the hypothesis implies that pi, p2, p3 are the vertices of a triangle, so, p1, p2 are adjacent on K2 and (7) has a solution; and the result in the theorem holds. I 3 Enumeration of Facets of the Convex Hull of a Given Set of Points Let {pl,...,pt} be a given set of points in IR' and P = < pl,...,pt > = convex hull of {pl,...,pt}. Let rank{p2 _ pl,...,pt - pl} = s. Then P has dimension s. If s = n, P is a full dimensional convex polytope in IRn. If s < n, a system of (n - s) equations characterizing the affine space of P can be determined, and by eliminating (n - s) variables using it one goes into the affine space of P in which P is a full dimensional convex polytope. In this reduced system the facets of P can be determined by the procedure discussed below. Each facet leads to a linear inequality constraint for characterizing P through a system of linear constraints. From these and from the system of equations characterizing the affine space of P in 1Rn, we gat a-linear constraint representation of P. So, we assume without any loss of generality that P is a full dimensional convex polytope in IRn. Let p = (p' +... + pt)/t. The point p is an interior point of P. Let Q be the polytope obtained from P by translating the origin to p, i.e., Q = < ql,..., qt > where qk = pk _ p, for k = 1 to t. Hence, 0 is an interior point of Q, and thus is not contained on any of the facetal hyperplanes of Q. Thus every facetal hyperplane of Q can be represented by an equation of the form alxl +... + anx n = 1 (11) with Q lying in the halfspace represented by alxl+...+aXn 1 (since 0 E Q). We will represent this facetal hyperplane by the vector of coefficients (ai,..., an) in (11). Then a = (ai,..., a,) is a vector representing a facetal hyperplane of Q, iff a is an extreme point of the following system of constraints aqk 1, k =1 to t (12) in which a is the vector of variables, and q1,..., qt are the data. And, alzx +... + anxn = 1 represents a facetal hyperplane of Q with Q lying in the halfspace defined by alxl +... + ann - 1, iff alxl +... + anzn = 1 + ap is a facetal hyperplane of P with P lying in the halfspace defined by alxl +... + anxn 1 + ap. Therefore, any algorithm for enumerating the extreme points corresponding to a system of linear constraints can be used to enumerate the facets of the convex hull of a given set of points. 4 Segments of a Polytope DEFINITION Let Q =< pl,..., pt >, where {pl,...,pt is a subset of extreme points of a convex polytope r. Qf is called a segment of r if the following conditions are satisfied. 6

(13) Dimension of = dimension of r For every pair of points in {pl,... pt}, they are adjacent in Q iff they are adjacent in r; i.e., adjacency on coincides with that on r. As an example cons r te hown in Figure 2, with 5 extreme points idThe covexull t polyto pe o i a segmenofit, because it satisfies both (13), and (14). As polytope is id to be a simle (or guloe if for each of its vertices, the number of incident edges is equalid to the dimension of the p olytope. A simple polytope is the set of feasible solutions of a the form (1) in hich the gh hand nstants vector b is nondegenerate as defined in linear p rmming literaturetl4 It is clear that in a simple polytopehe only pssle segment is te w e polynto mp poltope isonewhich has at least one vertex at which nu of inciden eg is stricly greater thn the dimension of the polytopeisone It is the set of feasible solutionf (1) in which the bovectr is degenerhate. A nonsimple polytope m'ay have a segment which is a proper subset Of it. Figure 2 provides an example of this In a simple polytope, every pair of edges with a,,,,cmover ine s d init ae. This property was used in Murty 13tochara erize and bud ing a ntrctive gorithm) eve ce of a simple polytope from its two dimensional n to. Inmnonmppolyte. Thembe pair of edog with a common vertex which donot lie together o anytwodm il f Th. air o edgesnejnig p4 and p3, and the other joining p4 and p2 in Figure 2 is an example of this. 4'and-P and the ot Fireaitper wthan extneme poisno Te lie are edges p > is a segment of this polytope. ~~~~~n osrci va l o ih)eryae In rmpe oltoe, ery r31tochrate iz(ndbfdul^oloetremyeprsoegs h~~~~~~~~~is oet a sam~~mzt inlseeo.I omp._~1~Tevi fegs oea T.P~~~~~~~ ot ruplepoltop frm ts to &en edes ~plpZp3p4 > pa emn ti oJop 7

A facetal hyperplane of a full dimensional convex polytope in IRn is a hyperplane in IRn containing one of its facets. Let Q be a segment of a full dimensional convex polytope r in IRn. It is possible that none of the facetal hyperplangs of r is a facetal hyperplane of f. As an example, let Q1 be the unit cube in IR3. Draw the normal to each facet of Q1 through the center of that facet, and take a point on it a little bit outside of Q1 as a new extreme point. This generates a convex polytope FI in IR3 with 14 extreme points (8 extreme points of Q1 and one extreme point on each of the 6 normal lines to the facets of Q1). It can be verified that Q1 (outlined with thick edges in Figure 3) is a segment of ri. Each facet of ri is a 2-dimensional simplex, but none of the facetal hyperplanes of ri is a facetal hyperplane of Qi. I Figure 3 Qf is the unit cube in IR3 with thick edges. ir is the convex polytope containing Qf as a segment, plus 6 new extreme points (only 3 visible in the figure) with one on the outer side of each facet of Q1. There can exist full dimensional convex polytopes r in IRn and segments Ql of r such that for every face F of r of dimension r, 3 r = n-, either F n = F, or F n Q has dimension r- 1. To construct an example like this, repeat the construction in Figure 3, replacing the unit cube with any full dimensional convex polytope Q2 in IRn. That is, draw the normal to each facetal hyperplane of f12 through the center (or any relative interior point) of the corresponding facet, and select a point on this normal just outside Q2 as a new extreme point. So, the number of new extreme points added is equal to the number of facets of Q2. Let r2 be the convex hull of the union of Q2 and all these new extreme points. It can be verified that none of the facetal hyperplanes of r2 is a facetal hyperplane of Q2, and that Q22 is a segment of r2 which satisfies the properties mentioned above. THEOREM 2 Let Q be a segment of a full dimensional convex polytope r in IRn, fQ # r. If r\Q is a convex set, then fQ = the closure of r\7f, is a segment of r; and Qf n Ql is a facet of Q. PROOF Since Q is a closed subset of r of the same dimension as r, and r\Q is convex; r\f has the same dimension as r. So, Q1 has the same dimension as r. 8

Since r\Q and Q2 are disjoint convex sets, they can be separated by a hyperplane. This hyperplane contains Q n Q1, and hence Q n ~Q2 is a face of both Q and Q1. Two convex polytopes of full dimension with a common face and with disjoint interiors form a union which is also convex, only if that common face is a common facet. So, Q n Q21 is a common facet of both Q and Qi. If x1 and x2 are two extreme points of F2Q at least one of which is not in Q, then x1 and x2 are adjacent on Q21 iff they are adjacent on r. And two extreme points of ~Q n Q2i are adjacent on Q (and hence on Qi) iff they are adjacent on r. These facts imply that Q1 is also a segment of r. I THEOREM 3 Let Q be a segment of a full dimensional convex polytope r in IR', Q2 5 r. If r\Q is the union of convex sets A1,..., A., where each At for t = 1 to r is a maximal convex set in the union; let At be the closure of At. Then At is a segment of r, and At n Q~ is a facet of both FQ and At, for each t = 1 to r. PROOF Since At is a maximal convex subset of r\Q, it is clear that r\At is convex, and as in the proof of Theorem 2 it can be verified that At is full dimensional. Since both At and r\At are convex and have disjoint interiors, they can be separated by a hyperplane. So, as in the proof of Theorem 2, it can be concluded that At n Qf is a common facet of both of them, for t 1 to r. If x is an extreme point of r in At and x2 is an extreme point of r in At, then the line segment {x: x = ax1 + (1 -a)x2, 0 < a < 1} C At, and hence x1 and x2 are adjacent on At iff they are aqjacgnt on r, for t = 1 to r. Also, two extreme points in At n FQ are adjacent in At iff they are adjacent in r since F2 is a segment of r. So, At is a segment of r for t = 1 to r. I THEOREM 4 Let Q be a segment of a full dimensional convex polytope r in IR". If a two dimensional face T of r has an intersection with Q that is more than an edge, then T is entirely contained in 0. PROOF Suppose Q has an intersection with T that is more than an edge, but does not contain all of T. Then one of the facets of Q splits T through its relative interior, and the intersection of T and that facet must lead to an edge of Q~ in the facet, that edge is not an edge of T, contradicting the segment property of Q. I THEOREM 5 Let r be a full dimensional convex polytope in IR3, and Q~ # r a segment of r. Then there exists at least one facet F of r such that FnQ has dimension - 1 (i.e., FnQ is either empty or Q contains at most an edge joining a pair of adjacent vertices on F). PROOF Since ~Q # r, there must exist at least one facet of r, F say, such that ~2 does not contain all of F. Since r is three dimensional, F is a two dimensional face of r, Then Theorem 4 implies that either F nQ = 0, or f contains at most an edge joining a pair of adjacent vertices on F. I How to Check the Adjacency of edges DEFINITION A pair of edges e1,e2 of a convex polytope are said to be adjacent on it if they have a common vertex, and if both of them together lie on a two dimensional face of that polytope. THEOREM 6 Let el, e2 be edges of K defined by (1) with a common vertex x1. Let x2, x3 be the other vertex on el, e2 respectively. Then el, e2 are adjacent on K (i.e., they form a two dimensional face of K, see 9

[14]) iff rank{A.j: j such that at least one of xj, or x2, or x3 is > O} is equal to two less than its cardinality..7 7 3 ) 3 PROOF Standard result, see [14]. This is an equivalent way of defining adjacency of edges. I THEOREM 7 Let the s-dimensional convex polytope K2 =< pl...,pt >C IRs, where each pk is an extreme point of K2 and all the points are distinct. Suppose el = the line segment joining p1 and p2, and e2 = the line segment joining p' and p3; are two edges of K2 with a common extreme point p'. Then, el, e2 are adjacent edges on K2 iff there exists a row vector c E IRJ and a 3 E IR', such that pl=cp 2=cp 3 = / Pt < if pt is an adjacent extreme point of p' on K2 different 15 from p2 and p3 cpk < p if p is not adjacent to pl on K2 PROOF By definition, a face of a convex polytope is its intersection with a supporting hyperplane.So, el, e2 form a two dimensional face of K2 iff there exists a hyperplane, H defined by cy = P say, which contains e1 and e2, and does not contain any other adjacent extreme point of pl on K2, and K2 lies entirely in one of the half-spaces defined by H. The system (15) is exactly a restatement of these conditigns, I Some More Results on Segments DEFINITIONS Let p' be an extreme point of a full dimensional convex polytope P in IRn. A hyperplane H which separates pl from all the other extreme points of P, and intersects every edge of P incident at p' in its relative interior, is known as an edge cutting hyperplane ( or EC hyperplane) for the extreme point pl of P. In this case P n H is known as an edge polytope ( or EP) of p' on P. The combinatorial structure of an EP for an extreme point pl on P is independent of which EC hyperplane for p' is selected. So, we will refer to it as the edge polytope or EP of pl on P. Two vertices on the EP of pl on P are adjacent on this EP iff the edges of P on which they lie are adjacent edges in P. THEOREM 8 Let x1 be an extreme point on a full dimensional convex polytope P in IR1, n > 3. S is a nonempty subset of edges of P incident at x1 satisfying the following properties. (i) S is a proper subset of the set of edges of P incident at x1, [SI > 2. (ii) For any face F of P containing x1, F # P, either S contains all the edges of F incident at x1, or the dimension of the convex hull of all the edges of F incident at x1 in S is < dimension of F. (iii) For at least one face F of P, F $ P, the convex hull of the set of edges of F incident at x1 in S has dimension between 1 and -1 + dimension of F. Let H be an EC hyperplane for x1 on P, and K, = P n H and K2 = the convex hull of the intersections of H with the edges in S. Clearly, K2 C K1. Then there exists a couple of extreme points of K2 which are adjacent on K2 but not adjacent on K1. PROOF Proof is by induction on n. First consider the case n = 3. In this case K1 is a two dimensional polytope, K2 is the convex hull of a proper subeset of extreme points of K1, and K2 contains only one 10

extreme point from some edges of K1. So, K2 must contain a pair of extreme points which are adjacent on K2 but not on K1, hence the theorem holds for n = 3. Now set up an induction hypothesis that the result in the theorem holds for polytopes of dimension - n - 1.^.We- will now prove that under the induction hypothesis, the result in the theorem also holds for the polytope P of dimension n. We consider two cases. Case 1: S contains no more than a single edge from any facet containing x1. In this case K2 has at least two extreme points, and no pair of extreme points of K2 are adjacent on K1. Hence the result in the theorem holds for P. Case 2: There exists at least one facet, F1 say, of P containing x1 such that S contains a proper subset of edges in F1 incident at x1, but at least two. Let S1 = S nF1. So, properties (i), (ii), (iii) hold for the subset S1 of edges of F1 incident at x1. Let K3 = F1 n H, K4 = convex hull of intersections of H with the edges in S1. By the induction hypothesis, there exist a pair of extreme points on K4, yl and y2 say, which are adfjacent on K4 but not on K3. But since F1 is a facet of P, K4 is a face of K2, so, yl and y2 are also adjacent on K2. However, since they are not adjacent on K3, they are not adjacent on K1. Hence the result in the theorem must hold for the convex polytope P of dimension n. By induction, the result in the theorem holds in general. I THEOREM 9 Let Q be a segment of a full dimensional convex polytope F in IRn, n = 3. If fl r, there exists an extreme point x1 of Q satisfying the property that a pair of extreme points on the EP for x1 on Q are adjacent on it, but not adjacent on the EP for x1 on r. PROOF Assume that Q 17 r. Notice that the set of extreme points on the EP for x1 on Q,is a subset of the set of extreme points on the EP for x1 on r. First consider the case n = 3. In this case Theorem 5 implies that there exists a vertex x1 on f2 such that there is a facet F of r containing x1, and f2 contains only one edge incident at x1, say el, from F. Since F is two dimensional, there is a second edge, say e2, incident at x1 in F, and this edge is not in Q. Let p',p2 be the points of intersection of el, e2 with an EC hyperplane H for x1 of r. The points, pl,p2 are adjacent extreme points of H n r, of these p' is in H n r but p2 is not. Both H n r and H n f are two dimensional, and H n Q C H n r. These facts imply that one of the two adjacent extreme points of p1 on H nfl satisfies the property that it and p1 are adjacent on H n Q but not on H n r. So, the statement in the theorem holds for n = 3. Now set up an induction hypothesis that the statement in the theorem holds for polytopes of dimension - n - 1, and their segments. We will now show that this implies that the statement in the theorem must also hold for F of dimension n and its segmentQ -7 r. We consider two cases. Case 1: There exists a face F of r of dimension r, 3 r n -1, such that F n Q is r dimensional and #F. In this case, clearly F n is a segment of F, both have dimension r; and F n is an r-dimensional face of Ql. By the induction hypothesis, there exists an extreme point x1 in F n Q, sich that there are two extreme points, pl, p2 say, on the EP of x1 on F n f which are adjacent on it, but not adjacent on the EP of x1 on F. The set of extreme points on the EP of x1 on F is a subset (those on a face) of the set of extreme points on the EP of x1 on r. These facts imply that pl,p2 are nonadjacent extreme points on the EP of x1 on r, but are adjacent on the EP of x1 on Q. So, the statement in the theorem holds for r and its segment Q in this case. 11

Case 2: For every face F of r of dimension r, 3 r _ n-1, either F n = F, or F n Q has dimension -r-l. Let x1 be an extreme point on Q such that Q does not contain all the adjacent extreme points of xI on r. In this.case the result in this theorem can be verified to hold by Theorem 8. Hence the result in this theorem must hold for the convex polytope r of dimension n under the induction hypothesis. It has already been shown to hold for polytopes of dimension 3. Hence, by induction, the result in the theorem holds in general. I THEOREM 10 Let Q be a segment of a full dimensional polytope r in IR". If Qf # r, there exists an extreme point x1 of Q and a couple of edges el, e2 incident at x1 in Q such that el, e2 are adjacent in 2, but not in r. PROOF By Theorem 9, there exists an extreme point, x1 say, of Q satisfying the property that a pair of extreme points, say yl, y2, on the EP of x1 on 2 are adjacent on it, but not adjacent on the EP of x1 on r. Let el,e2 be the edges of F containing yl, y2. Then el,e2 satisfy the result in the theorem. I How to Check Whether a Segment is the Whole Polytope Let r be a full dimensional polytope in IRn specified through a system of linear constraints, and {p1,..,pt} a subset of extreme points of F such that Q =< p,...,pt > is a segment of-Fr. To-check whether 2 = r, do the following for each r, 1 - r =t. Identify all the adjacent extreme points of p7 on Q~ using the result in Theorem 1, and hence find all the edges of S incident at pr. For each pair of edges of Q incident at pr, check whether they are adjacent on Q using the result in Theorem 7. For every pair of adjacent edges of Q incident at pr check whether they are adjacent on r using the result in Theorem 6. If one such pair is not adjacent on r, n # r by the result in Theorem 10, terminate. Otherwise continue. If the above work is completed for all r = 1 to t without encountering a pair of adjacent edges of Q which are not adjacent on F, Q2 = r, terminate. The whole work requires the solving of at most 0(t3) linear programs, and computing the ranks of an equal number of sets of vectors. 5 Algorithm for Enumerating Extreme Points Consider the convex polytope K defined by (1). This algorithm is initiated with one extreme point of K obtained by solving, for example, a Phase I problem using any of the polynomially bounded algorithms for LP. Beginning with this, the algorithm develops a list of extreme points of K, adding at least one new extreme point to the list per iteration, until all of them are in. At some stage suppose the list is {dl,..., d'}, consisting of r distinct extreme points of K. Each of these extreme points is a rational vector of size at most nL. Let K1 = < dl,..., dr >. At this stage we need to check whether there is an extreme point of K which is not in K1. This involves checking: is K C K1? Here K is defined through a system of linear constraints, and K1 as the convex hull of a finite set of rational vectors. If K1 is an arbitrary set of points, B. C. Eaves brought to our attention the paper of R. Freund and J. Orlin [9] which established that the problem of checking whether K g K1 is NP-complete. However, in our case every point in K1 is an extreme point of K, this makes our problem special and we are able to develop an efficient algorithm for it. Let (XB, XN) be a partition of the variables in (1) into basic, nonbasic parts for some basic vector for (1). Without any loss of generality we assume that XB = (Xi,..., Xm)T, XN = (Xm+li..., X)T. As explained in 12

Section 2, we will use this partition in the algorithm to look at the representation of K through a system of linear inequalities (as in (6)) in the space of the nonbasic variales XN. This partition is never changed during the algorithm. General-Iteration {d',..., dT} is the present list of extreme points of K. STEP 1 For k = 1 to r, let (dB, dk) be a partition of the vector dk into basic, nonbasic parts as in the partition (XB, XN) of the variables in (1). Here we check whether the dimension of K1 = < dl,..., dr > is < n - m = dimension of K. This step is carried out only if in the previous iteration this step resulted in the affirmative answer for the corresponding question at that stage, otherwise we go directly to Step 2 in this iteration. The dimension of K, = the rank of {dk - dN: k = 1 to r}. If it is n - m, go to Step 2, and in all subsequent iterations omit this step. If it is n - m - 1, there exists an fN = (fm+l,*... * ) 5 0 such that fN(dk - d ) = 0 for all k = 2 to r; find such a vector fN. Let fNdN = /. Then all the extreme points dl,..., d' in the current list correspond to points in the XN-space lying on the hyperplane defined by fNXN = /3. Now solve the two LPs (16) (17) Minimize fNXN Maximize fNXN subject to (1) subject to (1) - a - One or both of the LPs (16), (17) will have as an optimum extreme point a point not in the current list. Call it dcf+, add it to the list and go to the next iteration. STEP 2 In this step the algorithm tries to find a pair of points in the current list {d,..., d&} satisfying the pair are not adjacent on K, but adjacent on the convex hull of (18) the current list From the results in Section 2, this is done by doing the following for each of the ( ) pairs of points in {dl,..., dr} until one satisfying (18) is found. If the pair from the current list being examined now is p = (pj), q = (qj), they are not adjacent on K iff the rank of the set of vectors {A.j: j such that at least one of pj or qj or both are > 0} is strictly less than its cardinality - 1, see [14]. Checking this takes at most O(m3) effort. The points p, q are adjacent on the convex hull of the current list iff the following system in variables c = (c,..., cn) has a feasible solution, which can be checked by solving an LP. c(p-q) = 0 (19) c(p-dk) > 0 for all k such that dk:p or q If a pair of points satisfying (18) is found in the current list, let c be the vector obtained as the feasible solution for (19) for that pair. Now solve the LP 13

Maximize cx (20) subject to (1) The maximum objective value in (20) will be _ 7 = cp = cq > min {dk: k = 1 to r such that dk # p or q}. If the maximum objective value in (20) is > 7, an extreme point optimum for it is a new extreme point of K, add it to the list and go to the next iteration. If the maximum objective value in (20) is y, and an optimum extreme point obtained for it when (20) is solved is either p or q, the set of optimum solutions for (20) is a face S of K determined by Ax = b cx = Y (21) x - 0 In this case, p, q are the only two points from the current list feasible to (21) (this follows from (19) by the choice of c). Hence, its set of feasible solutions, the face S of K, contains only p, q from the current list. Since S contains p, q which are not adjacent on K (and hence not adjacent on S, since S is a face of K), the dimension of S must be _ 2. So, S, the set of feasible solutions of (21), has dimension - 2 and we only have two extreme points p, q on it in the current list. Therefore, by applying Step 1 discussed earlier, on (21) with p, q as the only known extreme points on it at this stage, we can get a new extreme point of S, this will be an extreme point of K since S is a face of K, add it to the list and go to the next iteration. If there exist no pair of points in the current list satisfying (18), then < dl,..., d' >, the convex hull of the current list, is a segment of K, go to Step 3. STEP 3 When we come to this step, K1 = < d',..., d, >, the convex hull of the current list, is a segment of K. Using the results in Section 2, find all the edges of K1. For every pair of edges of K1 with a common vertex, check whether they are adjacent on K1 using the result in Theorem 7. For every pair of adjacent edges of K1 check whether they are adjacent on K using Theorem 6. If every pair of adjacent edges of K1 is also adjacent on K, K1 = K by Theorem 10, i.e., the present list contains all the extreme points of K, terminate the algorithm. If we find a pair of adjacent edges of K1, el, e2 say, which are not adjacent on K; let d' be the common vertex, and d2, d3 the other vertices on them. So, in this case we have a row vector c in IR" and a 3 E IR1 satisfying cdl=cd2=cd3 = cdt < / if dt is an adjacent extreme point of dl on K1 different (22) from d2 and d3 cdk p3 if dk is not adjacent to d1 on K1 Now solve the LP Maximize cx (23) subject to (1) 14

The optimum objective value in (23) is - 3. If it is > /3, an extreme point optimum for (23) yields an extreme point of K not in K1, add it to the list and go to the next iteration. If the optimum objective value in (23) is /, and if the extreme point optimum obtained is not in K1, then again. we have a new extreme point, add it to the list and go to the next iteration. On the other hand, suppose an extreme point of K1 is obtained as an optimum solution of (23). Now consider the LP Maximize cx (24) subject to x E K1 We know from these conditions that the optimum objective value in (24) is 3. Among adjacent extreme points of d1 on K1, the only ones which are optimum to (24) are d2, d3. This implies that the set of optimum solutions for (24) is the two dimensional face F say, of K1 determined by the edges el,e2. However, since e1, e2 do not form a two dimensional face of K, the set of optimum solutions for (23) has dimension at least 3, and contains F. That set is the set of feasible solutions of Ax = b Cx = - -(25) X O Let A be the set of extreme points on F. The affine rank of A is 2, and it is the subset of extreme points of (25) in the present list. By applying Step 1 to the system (25) and the current known set of extreme points of it, A, we can get a new extreme point of the set of feasible solutions of (25). This set is the set of optimum solutions of (23), and hence it is a face of K, so, that new extreme point of (25) is a new extreme point of K, add it to the list and go to the next iteration. Each iteration except the final one generates one or more new extreme points which are added to the list. When the list has r extreme points, the work in Steps 2, 3 requires the solution of at most O((max{r, n})3) LPs each of size at most O(rnL), and hence requires at most O(r(max{r, n})3n4L) effort using the best available polynomial time algorithms for solving LPs. Thus when the list has r extreme points, the computational effort needed to either conclude that there are no new extreme points, or finding a new one, is at most O(r(max{r, n})3n4L). Thus the overall computational complexity of this algorithm to enumerate all the extreme points of K is at most O(S5n4L). Acknowledgement We are very grateful to Santosh N. Kabadi for many valuable discussions. 6 References [1] W. Altherr, "An algorithm for enumerating all vertices of a convex polyhedron", Computing 15(1975)181 -183. [2] M.L. Balinski, "An algorithm for finding all vertices of convex polyhedral sets", SIAM Journal on Applied Mathematics 9(1961)72-88. [3] C.A. Burdet, "Generating all the faces of a polyhedron", SIAM Journal on Applied Mathematics 26(1974)47 489. [4] N.V. Chernikova, "Algorithm for finding a general formula for the nonnegative solutions of a system of linear equations", USSR Computational Mathematics and Mathematical Physics 4, no. 4(1964)151-158. 15

[5] N.V. Chernikova, "Algorithm for finding a general formula for the nonnegative solutions of a system of linear inequalities", USSR Computational Mathematics and Mathematical Physics 5, no. 2(1965)228-233. [6] M.E. Dyer and L.G. Proll, "An algorithm for determining all extreme points of a convex polytope", Mathematical Programming 12(1977)81-96. [7] U. Eckhardt, "Theorems on the dimension of convex sets", Linear Algebra and Its Applications 12(1975)63 -76. [8] J. Edmonds, "Exponential growth of the simplex method for shortest path problems", University of Waterloo (Waterloo, Ontario, Canada, 1970). [9] R. Freund and J. Orlin, "On the complexity of four polyhedral containment problems", Mathematical Programming 33(1985)139-145. [10] M. Manas and J. Nedoma, "Finding all vertices of a convex polyhedron", Numerische Mathematic 12(1968)226-229. [11] T.H. Matheiss and D.S. Rubin, "A survey and comparison of methods for finding all vertices of convex polyhedral sets", Mathematics of Operations Research 5(1980)167-185. [12] K.G. Murty, "Adjacency on convex polyhedra", SIAM Review 13, no. 3(1971)377-386. [13] K.G. Murty, "The graph of an abstract polytope", Mathematical Programming 4(1973)336-346. [14] K.G. Murty, Linear Programming (Wiley, NY, 1983). [15] K.G. Murty, "Faces of a polyhedron", Mathematical Programming Study 24(1985)219-224. [16] K. G. Murty, Network Programming (Prentice Hall, Englewood Cliffs, NJ, 1992). [17] J.S. Provan, "Efficient enumeration of the vertices of polyhedra associated with network LPs" \ Technical report, Department of OR, University of North Carolina (Chapel Hill, 1991). [18] G. Swart, "Finding the convex hull facet by facet", Journal of Algorithms 6(1985)17-48. 16

I. i:;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' I 'I j l