Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra C.G.E. Boender, R.J. Caron, A.H.G. Rinnooy Kan, J.F. McDonald, H. Edwin Romeijn, Robert L. Smith, J. Telgen, and, A.C.F. Vorst Technical Report 89-24 July 1989

Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra C.G.E. Boender1 A.H.G. Rinnooy Kanl R.J. Caron2 H.E. Romeijn' A.C.F. Vorst5 J.F. McDonald2 R.L. Smith3 J. Telgen4 July 28, 1989 Abstract We present a class of shake-and-bake algorithms for generating (asymptotically) uniform points on the boundary of full-dimensional bounded polyhedra. We also report chi-square goodness-of-fit tests, and the results of simulations for some elementary testproblems.'Department of Operations Research, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands. 2Department of Mathematics and Statistics, University of Windsor, 401 Sunset Avenue, Windsor, Ontario N9B 3P4, Canada. 3Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117, U.S.A. 4Department of Applied Mathematics, Twente University, P.O. Box 217, 7500 AE Enschede, The Netherlands. 5Department of Mathematical Economics and Department of Mathematics, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands.

1 Introduction 1 1 Introduction In this paper we study the so-called shake-and-bake algorithms which, as far as we know, provide the only practical way of generating (asymptotically) uniform points on the boundary S of a full-dimenional polytope S. The fact that the points are uniformly distributed means that, in the long run, all subsets of S of equal size will be visited equally often, and subsets with positive measure will be visited with probability one. Part of the material which we present in this paper can be found in more detail in the technical reports Boender et al. [1988a,b]. For the so-called hit-and-run algorithms which generate asymptotically uniform points on the interior of S we refer to Smith [1984] and Berbee et al. [1987]. The relevance of generating points on 3, and the name shake-and-bake for this class of algorithms were mentioned earlier in Smith & Telgen [1981] in the context of detecting necessary constraints. Note that the shake-and-bake algorithms can also be used for the problem of optimizing functions which attain their optimal value on S, such as, for example, the minimization of a concave function over S (see e.g. Patel & Smith [1983]). Smith [1982] suggested the first shake-and-bake algorithm, referred to here as original SB, which generates a sequence of points which are asymptotically uniformly distributed on S. Given an iteration point z~ E 5, a random search vector v is generated from the uniform distribution on the surface of the unit hypersphere with centre z~. The intersection point yO of the line passing through z~ with direction vector v with 3 is accepted as a move point (i.e. x1 = yO) with probability cos,.o/(cos Oo + cos py), where O. and y, are the (acute) angles of the search vector v with the inward unit normals to S at z~ and ~y, respectively; else z1 = z~. The intersection point V~ is referred to as hit point. Hence, if the hit point y~ is accepted as a move point, then the next iteration point z1 is equal to y~, else the next iteration point z1 is equal to the current one z. In the next SB algorithm, limping SB, the move probability is equal to cosgo, while the search vector v is drawn from the same distribution as for original SB. The limitinmdistribution of the sequence of iteration points, as well as the sequence of move points, generated by limping SB is proven to be uniform on 3. The third algorithm, running SB, chooses the search vector from a distribution such that the hit point is atlway accepted as a move point, while maintaiing the important property that the distribution of the iteration points is asymptotically uniform on S. (See figures 1 and 2.) In this paper we give a proof for the uniform limiting distribution of the iteration points which applies to a complete class of shake-and-bake algorithms, including the three algorithms mentioned above.

1 Introduction 2 The outline of this paper is as follows: in section 2 we will describe the general class of shake-and-bake algorithms and discuss the above special cases in more detail. Section 3 contains a proof that the limiting distribution of the sequence of iteration points generated by the algoritms is uniform on the boundary of S. Results of the chi-square goodness-of-fit test are given in section 4, and in section 5 we present some experimental results.

1 Introduction 3 I.I I. I I Ia 1 Ia I Figure 1: Shake-and-bake algorithms original/limping SB Iteration 0: Iteration 1: Iteration 2: Iteration 3: Iteration 4: Iteration 5: Iteration 6: Hitpoint yo accepted -t iteration point x:= yo, 1z is a move point. Hitpoint y1 rejected -_ iteration point I2:= 2. Hitpoint yx rejected - iteration point 2:= z:. Hiitpoint p3 accepted _ iteration point z:= y3,:' is a move point. Hitpoint y2 rejected - iteration point z:= z. Hitpoint y3 accepted _ iteration point z4 = I3, z4 is a move point. Hitpoint i/4 rejected -- iteration point as = z4. Hitpoint ys accepted - iteration point z:= yI, Z6 is a move point. Hitpoint y6 accepted - iteration point z7 = y6, z7 is a move point. <\,'.I............. I v e,.4 v ___.!,;__ ___ _ _;;n. _ i,a,3 Figure 2: Shake-and-bake algorithm running SB

2 The shake-and-bake algorithms 4 2 The shake-and-bake algorithms 2.1 Introduction Consider a feasible region S C Rd (d > 2) defined by the following system of linear inequalities: au _ bA (i =,...,m) (1) where we have normalized the coefficients of the inequalities by choosing |ail| = 1. Assume that S is bounded, nonempty and of full dimension. Then S is a polytope that containts interior points, i.e. points for which the inequalities (1) are all satisfied as strict inequalities. We assume, without loss of generality, that all of the constraints are nonredundant, i.e. none of them can be dropped from the system (1) without changing S. Let S~ be the set of points in S for which exactly one constraint is binding, that is, ~= U{w: Uw= b;awjt < b,j i}. i=1 The shake-and-bake algorithms are based on a search from some point z E o in a feasible direction v, i.e. if constraint k is binding at a, then a'Lv < O. The intersection point y with the constraint hit first in the direction v is referred to as a hit point and becomes a move point with probability,(yjz). The hit point y is computed as follows. Let V, be the bounding hyperplane of the half-space Vi:= {w: a:< bi ( =,...,m). To determine y we compute all intersection points of the straight line passing through x with direction vector v, denoted by +v A E R with the hyprplanes Vi, (i = 1,...,m). It is easy to show that the intersection points correspond to the following values of A: ai= -, (i = 1,...,m). Clearly the intersection point corresponding to the smallest positive value of A is the hitpoint, which, for the algorithms described below, is an element of ~o with probability one.

2 The shale-and-bake algorithms 5 2.2 The class of shake-and-bake algorithms The class of shake-and-bake algorithms for polyhedral sets can be described as follows (see figure 1): Step 0: Find some point z~ E. Define k as the index corresponding to the constraint that is binding at z~. Set n = 0. Step 1: Generate a direction vector v a follows: Select a random point z from an absolutely continuous probability distribution over the intersection of V^ with the surface of the d-dimensional unit hypersphere with centre z". Set v:= z - n. Step 2: Determine the hit point y" as follows: bi - allf".= (i = 1,...,m) at, r: arg mi.n m{A > 0) yn:= zn + AV Go to Step 4 with probability 0(y"lz"). Step 3: Set zn+1:= ", i.e. the next iteration point is equal to the current one. Go to Step 5. Step 4: Set zn+:= y and k = r, i.e. ~n becomes a move point. Step 5: Set n:= n + 1 and go to Step 1. Note that from the description of the algorithms it can be concluded that the sequence of iteration points defines a Markov chain with a stationary transition density function and continuous state space 0, which will be useful in the subsequent analysis of the algorithms. Because of our assumptions on the set 5, there is a one-to-one correspondence between a feasible direction from a particular point in 30 and a hit point. We will define our class of algorithms by imposing conditions on the distribution of the search directions and on the move probability function 0(ylz). Without loss of generality we write the density of the absolutely continuous component of the distribution of hit points in the form: A(YI:) =f(z y) 1 - where Vy:= {wU: aIW = b,} is the hyperplane that is binding at y E 3~. Note that b, - a4z is equal to the distance from z to V,,. Also note that (b, - a4)/11z - yll = cos O., where cos b, is as described in section 1. The move probability function will be written in the form t11 - y1

2 The shake-and-bake algorithms 6 where V. is the hyperplane that is binding at z E S. Denote the density of the absolutely continuous component of the distribution of the v-step transition probability of moving from z E o to a neighborhood of y E ~o by p(')(ylz). The 1-step transition density function p(yiz) = p(l)(ylz) is then given by: p(ylV) = 0(yIz)p(yvz) = h(z, y)(b. - a y)(bv - az) h(z, y) llOvll^1 11Z - yljd+l where h(z, y)= f(z, y) g(z, y) The class of shake-and-bake algorithms we discuss in this paper is defined by imposing the following conditions on the function h: 1. h(z,y)is symmetric in and y, i.e. h(z, y)= h(y,z) for all Z,y E S 2. h(z, y) is uniformly bounded from below by zero, i.e. there exists a constant 6h > 0 such that h(z,y) 6h for all z, y E 5, Z #y. Of course we also require 0 < 3(ytl) < 1 for all z, y E o~. It is easily shown that the first condition implies that p(')(Iyz) = p(")(zy) for all z, E o, where v = 1, 2,... The class of shake-and-bake algorithms which satisfy conditions 1 and 2 will be referred to as SB algorithms. 2.3 Some special cases In this section we will describe three specific SB algorithms. Original SB In this algorithm, the direction vector v has a uniform distribution over the feasible directions. The distribution of hit points is given by 2 2(b1 -r 2) Po(Yl,) = Cd II, - 11' where Cd = r2r1 is the surface area of a d-dimenional hypersphere with unit radius. The move probability function is given by

2 The shake-and-bake algorithms 7 (b. -;a/) 4o(vlz) = ( y) o )-(b - a' y)+ (b -a) So for this algorithm we have ho (z,~y) = 2 11 - lvII ho(. y) = Cd [(be - a' y) + (bv - > with aho = C > 0 and the l-step transition density function is equal to: PO(Ylz) = 2 (b - a' )(b- 4z) Cd, il - yl|j [(b, - a.y) + (b, - a4)] Limping SB In this algorithm the direction vector has the same distribution as for original SB, i.e. PL(yIZ) = Po(yIz). The move probability function is given by PL(yIZ) = ba-;. 11, - yll - Note that 3L(ylz) does not depend explicitly on y. Thus, the hit point need not be computed unless it is accepted as a move point. For this algorithm we have 2 hL(Z, ) = so that = 2 > 0 and PL(X ) = 2 (bg - 4y)(b. - 4z) Cd IIz - pIId+1 Running SB A drawback to original and limping SB is the fact that not every hit point is a move point. This means that, in general, several random directions may have to be considered before a move point is generated. It also means that the rate of convergence of the iteration points to being independetly and niformly distributed will be slow, since successive iteration points will be highly correlated. The algorithm running SB solves this problem by taking

2 The shake-and-bake algorithrr 8 R(IZ) = 1. The distribution of the direction vector is then chosen with the goal of obtaining a uniform limiting distribution. In particular, the random direction vector v is obtained as follows: Draw a point u from a uniform distribution on the (relative) interior of the intersection of the d-dimensional unit hypersphere centered at the origin and the hyperplane {w: Guw = 0O. The search vector v is defined as the vector with Euclidean norm 1 whose projection on the hyperplane {w: a' w = 0} is equal to u, under the condition that a'v < 0. We will describe this in more detail below. This choice of distribution of the direction vector leads to the following transition density function: PR(YSi) = (b, - aiy)(b| - 42) Bd —1 11z - yJlld+ where Bd r-) is the volume of a d-dimensional hypersphere with unit radius. Note that for this algorithm hR(z, y)= so that s6h = B > 0. In this algorithm, we need to generate a point u from the uniform distribution on the (relative) interior of a (d - 1)-dimensional unit hypersphere contained in some hyperplane, say {w: cdw = 0} (with Ilcil = 1). This point can be obtained in the following way: First, draw a point i from the uniform distribution on the surface of a d-dimensional unit hypersphere centered at the origin. The point (I- cc)u/ll((- cC)ull, which is the projection of u on the hyperplane {w: dw = 0}, rescaled to have norm equal to 1, is uniformly distributed on the surface of the (d- 1)dimenaional unit hypersphere centered at the origin contained in that hyperplane. This point is now rescaled to have norm r, where r is chosen such that the resulting point u has the required distribution, which means that r-1 ha to be drawn from the uniform distribution on (0, 1]. So we have: r (I - ca)u r (I - cC)) 1 - l - ce)All - %/

2 The shake-and-bake algorithm 9 and the corresponding direction vector is given by: v = u - Vl-u- ( *( c + r c. t- (Ci V)l(c/i 2 2.4 Limping and running SB reexamined Given that the present iteration point is z, the conditional probability that the next hit point is also a move point is given by P(z) = 0(yI.) p(yxt) dy = / p(yla) dy. Since for all z, p(ylz) > 0 for all V in a subset of S~ of measure greater than 0, it follows that for all SB algorithm P(z) > 0 for all z. Since the expected value of a random variable having a geometric distribution with parameter q is equal to (1 - q)/q, the expected number of iterations required to generate a move point from z is equal to 1/P(z), so that this expected value is always finite. For any shake-and-bake algorithm, say A, with transition density function p(ylz) we can define another algorithm A generating only the move points corresponding to A. (Obviously, when P(z) = 1 for all z (e.g. when A = running SB) the two algorithms are the same.) The transition density function (yjlz) of algorithm A can be expressed in terms of p(ylz) and P(z): p(vyl) = p(lz)+ (1 - P(Z))p(y) + (1 - P(z))2p(yz)+... = (1 - P(z))p(ylz) isO = p(p(lI). It follows that h(z, y) = h(z, y)/P(z). Of course, if the function h satisfies conditions 1 and 2 in section 2.2 then algorithm A is an SB algorithm. If A is an SB algorithm, then so is A if and only if P(z) is independent of z. For limping SB the move probability PL(z) is equal to: P ( ) 2B,-1 PLc() = ~ This move probability is independent of, so the algorithm generating the move points of limping SB is also an SB algorithm. Comparing the transition density functions of limping and running SB we observe that limping SB = rnning SB (see figures 1 and 2).

2 The sharkeand-bake algorithms 10 2.5 Computational efficiency To determine a next iteration point all shake-and-bake algorithms have to generate a search vector. If the acceptance probability function of an algorithm depends explicitly on y, then the hit point corresponding to the search vector has to be computed. If this is not the case, then the hit point only needs to be computed if it is accepted as a move point. For the three algorithms described above, we have that the generation of a search vector requires 0(d) time. Due to the 2d multiplications for each inequality of S the computation of the intersection points requires 0(md) time. This implies that for original and running SB the computation of an iteration point requires 0(md) time. For limping SB the acceptance probability does not depend explicitly on y, so the expected computation time per iteration point depends on the probability that a hit point is also a move point. Since 1/PL(z) V/(di + 1)/2 for large d, we have that this probability is 0(1/Vd), so the expected computation time per iteration point is 0(md). The foregoing analysis seems to suggest that, in some sense, limping SB is better" than original or running SB. However, there will be a difference among SB algorithms in the rate of convergence to the uniform distribution. As noted before, the convergence rate of algorithms for which not every iteration point is a move point (e.g. original and limping SB) may well be much lower than for algorithms generating only move points, such as running SB. This issue will be addressed in some more detail in the next section.

3 The uniform limiting distribution 11 3 The uniform limiting distribution In this section we prove that for all SB algorithms the random sequence {X'} of iteration points converges to the uniform distribution on ~, independently of the starting point in the set t. We use the following theorem: Theorem 1 If (a) there eists a scalar > 0 and a v > 1 such that p()(yVI) ) 6 for all, y,E and (b) p(ylz)= p(zly) for ll z,y E, then the sequence {Xi}O of points has a uniform limiting distribution on S~. Proof It follows from (Doob [1953], p. 197) that (a) implies the existence of an asymptotic stationary distribution. Analogous to the proof given in (Smith [1984], p. 1300) it follows that (b) implies that the uniform distribution is the unique stationary distribution. o As was noted in section 2.2, condition (b) is satisfied. What remains is to find a 6 > 0 and a v > 1 such that condition (a) is satisfied. Theorem 2 proves that (a) is satisfied with v = 4. Theorem 2 There eists a scalar 6 > 0 such that p(4)(ylz) > ) for all z, y f. The proof will be given after the following two lemmas. Lemma 1 There exists an io > 0 such that for every: E 6~ there exists an indez: j such that bj - a'z > io. Proof Suppose such an o does not exist. This means that for all e > 0 there exists an z, E ~ such that bj - axz, < t for all j. So for all n = 1,2,.. there exists an 8,n E o such that bj - a'dXz < for all. Since 3 is compact, we know that the sequence {zf}t1I has a limiting point zo E 3 for which bj - ajzo = 0 for all j. Now suppose y is an interior point of S, i.e. bj - a'y > 0 for all j. Then zo + a(y - zo) is an interior point for every a > 0 since bj - a'(Zo + a(y - zo)) = a(bi - agyl) > 0 for all j. This implies that S is unbounded. Contradiction. o Lemma 2 For every i theemist an > 0 such that the st i:= {z E Vi: bj - az > i Vj # i} has positive (d - l)-dimensional Lebesgue measur. (See figure S.)

3 The uniform limiting distribution 12 Figure 3: V Proof Choose an arbitrary constraint i. We know that constraint i is nonredundant, so there exists an zo for which bi- azo = po < 0 bj - azo > 0 ( i i). Suppose zl is an interior point of 5, so bi - azl = 1I > 0 bj - azl > 0 (j # i). Choose z. =lzo - =. OzI - -^ JAI - JsO which is a convex combination of o and z. So we have Isi^so Isi-so1 6,- a^>- (' )-., _ ( _b l; - Plo (l o - k) = o bj - 2z > O (yj ( i). So bi - aiz' = 0 and bj - a'z' > 2.2 for all j # i, where i:= min(6j - a,')/2 > 0. For all z E Vi for which 1z - z'll < 4, we have

3 The uniform limiting distribution 13 bi - az = 0 bj - ajz = bj - a;z + >a(z - z) > 21 - 1i = a (j f i) which implies that z E V'. Hence, the et V' has positive (d - 1)-dimensional Lebesgue measure. o Corollary If we define ~:= min{o, minn } > 0 then for all 0 < c < i and for all i the set V has positive (d - 1)-dimensional Lebesgue measure. Corollary If we define ~:= min{^omin 4t} > 0 then for all 0 < e < ~ and for all i the set VZ has positive (d- 1)-dimensional Lebesgue measure. Proof of Theorem 2 For all z,y E ~ P(4)(yjz) > f P (zil z)p(z ) p(z3lz) p(ylz3) dz, dz2 dzl. Suppose z E Vi and y E V-. Choose some 0 < e <. It follows from lemma 1 that there exists a k # i and an 1 j such that b& - az > e and bl - a y > e. Choose some index t # k, I (see figure 4). Define rS as the maTimal distance between two points in S: rs:= ma llh - hll. m~~E~S

3 The uniform limiting distribution 14 ~z.. o'-.. \ 1/ ~ * A Figure 4: From z to y in 4 steps Then: 1. p(zl1z) = h(:zz)(bi - azl)(bk - a',|), 2 ~p(z.z).. h(z " z1" > h' d+1 for all zi E Vk satisfying bi - a'zl > e. 2~. ~(bl - y)(i - a'zS) 2. P(yjiZ3) = h(zS, y)( I > Sa d II,, - Yll"+' >,.+, for all z3 E VI satisfyig bj - ajz3 > e. 3. p(z2 l,) = h(z,, z2)(bk - Z)(bt - ) > a s -) IIzi - z211' i+ " for all zL E VI satisfying bt- az> > c and for all z2 E Vt satisfyng b -a'z2 > e. A4. p(z31,jl,-) =,,,,)(bt -.;.a)(bb - gaz,) 2) 4. P(LZ|3Z) = h(z2,,3) I z ^ — > s h for all z Vt satisfying b - az; > e and for all z3 E V satisfying bt - az3 > e. So we have pC)(ylz) 1f44 +4I dz dz2 dz > *4+4 m lI )m (Z m-l( ) Sh 4 +4*. / )

3 The uniform limiting distribution 15 where md() denotes the d-dimensional Lebesgue measure of a set. Using e > 0, rs < oo, 6h > 0, and the corollary of lemma 2 we know that 6 > O. o The value of 6 can be used to compare the convergence rate of the SB algorithms using the following theorem from Doob [1953]: zYE, then Pr Xm E AIX~ = z~} - I < (1- 1 m_;)) 1 for all A C? with positive (d - 1)-dimenional Lebesgue measure, and for all z E 0. Clearly, a larger value for S corresponds with a faster rate of convergence to the uniform distribution. We now rewrite the expression for S given above as follows: a = af, * as where'S 6s = 4 * (mpmmi (Vs)) only depends on the region S, and not on the particular algorithm used. This means that we can compare the convergence rates of the SB algorithms by comparing the values of 6,. Recall from section 2 that ^o = C I 6 == C uand h, = L1 It is easily seen that, for d > 2, the following holds: 6^o < 6 < 6^a. Moreover, as the function hR(z,y) is a constant, and the move probability equals one for this algorithm, we have for all SB algorithms, since fj p(glz) dy < 1 for all SB algorithms. Thus, taking into account that we are discussing lower bounds, we may conjecture that the sequence of iteration points generated by running SB converges faster to the uniform distribution than the sequence of points generated by limping SB, which in turn converges faster to the uniform distribution than the sequence generated by original SB. Furthermore,

3 The uniform limiting distribution 16 running SB has the fastest rate of convergence of all SB algorithms. It should however be noted that for a specific region S it might be possible to obtain a better lower bound than the one given in theorem 2, specifically for algorithms having a nonconstant function h associated with them (like for instance original SB). Therefore, we should be careful in drawing strong conclusions from only the comparison of values for h, when h is not equal to a constant, at least until some empirical results are taken into account.

4 Ch-square tests 17 4 Chi-square tests In this section we will compare the performance of the three algorithms original, limping and running SB, measured by the rate of convergence to the uniform distribution. The three algorithms were run on two hyperrectangles, of dimension 5 and 10 respectively, of the following form: 0 o< <i (i = 1,...,d). We have chosen to test the algorithms on hyperrectangles because the area of the facets of these polytopes can be calculated analytically. Any two iteration points are correlated, but the serial correlation between two points Xi and Xi+N goes to sero as N goes to infinity. So, to avoid serial correlation effects, we only sample one of every N iteration points, for different values of N. If N is large enough we can assume that the random variables XN, X2N,.. are i.i.d. uniform. In that case we can use a chi-square goodness-of-fit test to test uniformity. We divided the hyperrectangles into a number of cells, according to the formula of Mann & Wald (see Mann & Wald [1942]). Each facet was divided into a number of exactly equal-sized cells, and the number of cells per facet was chosen such that the sizes of cells in different facets were almost equal. For the first testproblem (of dimension d = 5) we chose N = 10, and we generated samples of different lengths n. For every sample size, we generated 5 different samples and performed the chi-square test at a significance level of 5%. The number of times a chi-square test was rejected is reported in table 1. n original SB limping SB running SB 200 2 2 0 400 1 1 1 600 0 1 1 800 0 1 0 1000 1 2 0 Table 1: d =,N =10 For the second testproblm (of dimenion d = 10) we used N = 10, 25 and 50. Again, the number of tim a chi-square test was rejected is reported. See table 2. An observation drawn from these tables is that in almnt all caes the number of rejections of the null hypothesis is minimal for running SB. This means that the convergence of the distribution of the points generated by running SB to the uniform

4 Chi-square tests 18 n oriinal SB limping SB running SB N 10 25 50 10 25 50 10 25 50 200 4 0 0 5.2 1 2 0 0 400 3 1 1 3 1 1 2 1 1 600 5 3 1 5 1 1 1 1 1 800 4 3 1 5 2 2 2 1 1 1000 4 2 0 4 5 0 3 2 1 Table 2: d = 10 distribution is faster than the convergence of points generated by original or limping SB. This confirms our theoretical analysis of convergence rates in section 3. The convergence rate of original and limping SB appears to be amost equal. Numerical experiments (Caron & McDonald [1987J) have suggested that the average number of iteration points required to generate a move point grows faster (as a function of the dimension d) for limping SB than for original SB. Thus, the value of N necessary to eliminate serial correlation effects will also grow faster with growing d for limping SB. This could mean that, for growing d, original SB will perform better than limping SB, at least for smaller values of N. Thus the performance of original SB as opposed to limping SB still remains an open question, as our experiments fail to confirm the conjecture of section 3. To sunmmarise, we can conclude that running SB outperforms both limping SB and original SB.

5 Experimental results 19 5 Experimental results We conclude the pap ith some dditionaresults of the algorithm running SB. We let the figures speak for themrelves. r.a I l * me e* - * - m-*.*e. e. ~... lmm e. ".. * e m.. a _ ~ e oe. dos.. ~. o.. _ m. e, * 9* # Figure 5: 100 iteration points ] m m - e m em m _|,......._.._. e I a —- W' * __-. L m m m m m m - m m Me eME06 ao Figure 6: 500 iteration points

UNIVERSITY OF MICHIGAN 3 9015 04732 7302 References 20 References [1] H.C.P. Berbee, C.G.E. Boender, A.H.G. Rinnooy Kan, C.L. Scheffer, R.L. Smith, and J. Telgen. Hit-and-run algorithms for the identification of nonredundant linear inequalities. Mathemtical Progrmming, 37:184-207, 1987. [2] C.G.E. Boender, R.J. Caron, J.F. McDonald, R.L. Smith, and J. Telgen. A class of shake-and-bake algorithmr for generating random points on the surface of a bounded region. Technical Report WMR 88-08, Department of Mathematics and Statistics, University of Windsor, 1988a. [3] C.G.E. Boender, A.H.G. Rinnooy Kan, H.E. Romeijn, and A.C.F. Vorst. Shakeand-bake algorithms for generating uniform points on the boundary of bounded polyhedra. Technical Report 8826/A, Econometric Institute, Erasmus University Rotterdam, 1988b. [4] R.J. Caron and J.F. McDonald. Private communication, 1987. [5] J.L. Doob. Stochastic Processes. Wiley, New York, 1953. [6] H.B. Mann and A. Wald. On the choice of the number of class intervals in the application of the chi-square test. The Annal of Mathematical Statistics, 13:306-317,1942. [7] N.R. Patel and R.L. Smith. The asymptotic extreme value distribution of the sample m;nimtnu of a concave function under linear constraints. Operation Research, 31:789-794, 1983. [8] R.L. Smith. Private communication, 1982. [9] R.L. Smith. Efficient Monte Carlo procedures for generating random feasible points uniformly over bounded regions. Operations Research, 32:1296-1308, 1984. [10] R.L. Smith and J. Telgen. Random methods for identifying nonredundant constraints. Technical Report 81-4, Department of Industrial and Operations Engineering, College of Engineerng, The University of Michigan, Ann Arbor, 1981.