Optimizing Connections in Solar Power Systems J. R. Birge* and V. Malyshko** Technical Report No. 82-9 * Department of Industrial and. Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 **Byelorussian State University Minsk 22080 USSR. May, 1982

Optimizing Connections in Solar Power Systems J. R. Birge The University of Michigan Ann Arbor, Michigan 48109, U.S.A. V. Malyshko* Byelorussian State University Minsk 22080 USSR Abs tract We consider the problem of minimizing cable connections between a central computer and a field of heliostats in the design of solar power systems. This practical task can be modeled as a p-median problem with additional constraints in a weighted graph. We compare an exact branchand-bound method with two approximate algorithms. For the latter two methods, estimations of time complexity and accuracy are presented. Computational results are shown which should be useful in the design of such large-scale power systems. * Visiting scholar under the IREX program for 1981-82 at The University of Michigan.

1. Introduction A terrestrial solar thermal system consisting of a field of heliostats used to reflect sunlight to a central tower receiver is considered. The receiver contains a liquid which is heated to produce steam which in turn drives a turbine as in a conventional steam generating plant. Pilot systems have been built in many countries [2, 3, 8, 11] and have been studied for the optimal design of heliostats and configurations [13, 16]. The heliostats must be under constant control in order to maintain their reflective accuracy in directing sunlight to the receiver. Besides this function, such control makes the following operations possible: initial powering each morning according to given solar radiation intensity; following the sun's movement during the day; switching off of the system whenever solar radiation falls below a minimum level for a given length of time; connecting and disconnecting separate groups of heliostats to regulate the amount of power required; and so on. In the earliest plants [8], each heliostat was independently steered. In large systems, this cost becomes prohibitive and some central computer-based control is necessary [4]. With this system, costs can be further reduced if micro-processors are used as intermediary data concentrators instead of having each heliostat directly connected to the central computer. One possible configuration is that of the Smith helioelectric farm [17]. In their proposed plant, a central computer is linked to 600 minicomputers, each of which is connected to 16 microprocessors. The microprocessors control 32 heliostats each.

2 It should be emphasized that the minimization of expensive cable lengths is very important for large power plants. For example, to connect 21,000 heliostats independently to a central computer from a 1500 meter by 1500 meter field, 9,000 kilometers of cable are required [20]. This amount of cable may be reduced twenty fold by constructing a hierarchical system including microprocessors and by employing optimization methods to the design of that system. In this article, we investigate methods for organizing connections in a two level control system for a field of heliostats to minimize the lengths of additional cable. Practical task. We are givenn+l points, (xi, yi), i = 1, 2,...,n + 1, where, for i = 1, 2,...,n, the point is the site of a heliostat or microprocessor, and, for i = n + 1, the point is the site of the central computer. We must allocate microprocessors according to the following conditions; (a) Every heliostat must be connected with a microprocessor and every microprocessor must be connected with r heliostats; (b) Every microprocessor must be connected with the central computer; (c) The lengths of connecting cables must be minimized. In our discussion, we propose three alternative approaches: 1) An exact method which reduces the task to a p-median problem for a weighted graph and solves this using the simplex method andbranch-and-bound '[5, p. 112].

3 2) An approximate algorithm based on local optimization [17]. 3) An approximate algorithm based on constructing the minimum spanning tree using the algorithm in [1, p. 172] and sequentially allocating p-medians to the vertices of this tree. When n is large, the first algorithm may be inefficient, and using the approximate algorithms may be desirable. We present worst case estimations of the time complexity and accuracy for Algorithms 2 and 3. We also present computational results on a series of randomly generated problems. These results indicate that Algorithm 3 has the least average time requirement and that its resulting solution may achieve a sufficiently accurate result. The cost of additional optimization upon this solution should be weighed in specific applications. 2. Model Description and Solution Methods Let V be the set of given points, vi, with coordinates, (xi, y,), where i = 1, 2,...,n + 1. The Euclidean distance pij between any pair of points, vi, v., is given by d(v, 2 + ((1 d (ViX Vj) = (Xi -X) + (yi-y ) * (1) We consider the complete graph G.(V,E),defined on the given vertex set, V, where every edge in E has associated with it a nonnegative distance. Let p be the number of medians (excluding the central point) which must be placed on the given set of vertices V. Then, n -p n (2) n P- = p, or p = r+l r

4 The original practical problem may be reduced to finding the subset V* C V such that P (V*) = min{a(V )}, where P P (3) c(V ) = Z d (V, v.), and P P J iv.CV/V J P d(Vp, v) = J min {d(vi, v.)}. vv. V 1 p This problem is known as the p-median problem. We, however, have the additional requirement (a) above that each median (microprocessor) must be connected with exactly r vertices (heliostats). This problem can also be formulated as a binary integer linear program. We define the decision variables as xij = 1 if vertex v. is assigned to vertex vi, J 0 otherwise (4) Letting d.. = d(v(i), v(j)), the problem is: 1j

5 n+l n+l min Z Z d. x.. (5) j=l i=l 1 1 n+l subject to Z x.. = 1, j = 1,...,n + 1 (5.1) i=l 1J n x.. < r, i = 1,..., n + 1 (5.2) j=l 13 n Z Xii= P Xn+l, n+l = (5.3) xj < x, i = 1,..., n + 1; j = 1,..., n + 1 (5.4) x.. {0O, 1}, i = 1,..., n + 1, j = 1,...., n + 1. (5.5) Constraint 5.1 indicates that every heliostat is assigned to a (microprocessor). 5.2 constrains the microprocessor to be connected to at most r heliostats. 5.3 yields p total microprocessors and one central median, and 5.4 forces the heliostats to. be connected to places of microprocessors. 5.5 insures that a heliostat is either connected to one other heliostat or not. 2 Problem 5 is a binary integer linear program with (n + 1) variables. This can be solved exactly by a direct branch-and-bound procedure, or it may be solved by the simplex method by relaxing constraint (5.5) to 0 < x. < 1. In the latter case, an exact solution may be found by further branching on the values of fractional x..i The number of additional steps may be small, as reported in Revelle and Swain [16,]. This

6 approach tis used in Section 4. In the following, we will denote this method as Algorithm 1. When n is large and the linear programming solution has many fractional values, branch-and-bound procedures may prove inefficient in finding a solution. In this case, some heuristic procedure may be necessary. One such procedure that we will use here is due to Teitz and Bart [18]. We have extended this method to the capacitated case here in which every median must be connected to r vertices. The algorithm proceeds by starting with a given set of p medians and of vertex assignments to those medians. The first phase of the algorithm is to determine whether switching two vertices assignments can lead to an overall reduction in the total distance. For this algorithm, we use a different definition for the value of the p-median assignment. For a specific instance I of the problem, we let: a(V ) Z ( Z d(v., v.)), (6) v. V v.CV. J 1 P 3 i1 p j 1i where V. is the subset of r vertices connected to the median vi, and 1 the medians are vT(l), vT (2)...,''' (p) This definition is used to explicitly incorporate the capacity constraint on microprocessor connections.

7 Algorithm 2. Step 1. Assign vertices to p medians such that each median is connected to at most r vertices. Let the median set be V = {v v (2, ' v(p} Order all vertices vi, i < n, vi 4 Vp by V, vi2,..., v. Let j = 1. 1 " p. 1 2 n-p Let k = 1. Let V = V. P P Step 2. Replace median vT(k) by vj. Let V = V - {vT } U {vi } T k.) ij p p T(k) 1' Allocate each vertex v ~C V to the closest median vertex v C V' that is connected to less than r vertices. q P Calculate a (V'). If a (V') < a (V ), then let V" = V'. p p p P P If k < p, then, let k = k + 1 and repeat. If k = p, then, let V = V, let k = 1. If j < n-p, let j = j + 1 and P P repeat. If j = n-p and V has changed since Step 1, then p go to Step 1. If V has not changed, go to Step 3. Step 3. For every pair of non-median vertices, (vi, vj), i 4 j such that vi ~ Vk and v. ~ VP, k $: If d(vi, vk) + d(vj, vk) < d(vi, vk) + d(vj, vk), then let a) Vk = k - {v} U {v}, b) V = V - {v} U {v}. j i Go to Step 4. Step 4. STOP. V is an approximate set of p-medians, and V (1) V (2)..., VT(p) are partitions of vertices to those medians. We let a2(I) = O(Vp) for an instance I of the problem.

8 This algorithm results in essentially a 1-optimal assignment of medians. Further A-optimal solutions as in Lin's [12] procedures for the travelling salesman problem may also be found, but they require substantial increases in computational effort. The heuristic algorithm above 2 requires (n-p) p steps for each pass through Step 2 and (n-p) steps in Step 3. The algorithm must terminate since at every cycle an improved solutions is considered, and since there are a finite number of possible starts for Step 2. The number of these possible starts is ( ), the number of possible median sets. The main idea of the third method is to reduce the given initial problem on the complete weighted graph G(V, E) to the solution of an approximate variant of the p-median problem on a tree. Let T(V, E) be a minimum spanning in G(V, E), which may be constructed using Kruskal's algorithm [1, p. 172]. Let (vi, v.) c E. Removing the edge (vi, vj) from T divides the tree T into 2 components, Ti(Vi, Ei) and Tj(Vj, Ej) such that v.i Vi, vj, and V U V = V. Proposition 1 [11]. If IVi. > IVj., then the median v* of the tree T belongs to V.. Proof: Alternatively suppose that the median v* C V.. Then, the value of functional (3) will be increased by the value of the product of the length of edge (v., vj) and the difference IVil - IVj.. In other words, c(v*) will not be minimized. In the following algorithm, we use the postorder traversal of T defined below.

9 Definition ([1, p. 54]). Let T be a tree having root r with sons Vl, v2',..,,k' k > 0. In the case k = 0, the tree consists of the single vertex r. A postorder traversal of T is defined recursively as: 1) Visit in postorder the subtrees with roots, vl, V2,...Vk, in that order, 2) Visit the root r. Algorithm 3. Step 1. Construct the minimum spanning tree T of the graph G(V, E) using Kruskal's algorithm [1, p. 172]. Vertex V 1 will be the root of T. n+l Step 2. Employing the postorder transversal of T, assign each vertexvicTa weight W(vi) which equals the number of its descendants, in other words, the number of vertices lying on all paths from v. to the leaves. Allocate the first median v* to the vertex v. Let a = 1 and S = (. ~1 ~~n+l Step 3. Remove the edges adjacent to V* and let vjl, v,, v be the vertices formerly adjacent to v* Include in S the set of subtrees, T1, T2,...,Tk, with roots vjl, vj2,....vjk

10 Step 4. Choose from S, the subtree TO such that: W(v ) = max {W(v. )}. JO v T.cS i Let S = S Step 5. In subtree - T* T0f T * find the vertex V such that ol a A(v ) = min {A(v.)} where vi0T A(v.) = 12W(v ) - W(v )I. (7) 1 1 J0 v is then the vertex with the most nearly equal number of ancestors and descendants. Step 6. Allocate the median V.+ to the vertex v. then let k = g + 1 and go to Step 3. Step 7T Let {v v *,,v } be the set of medians 1' 29''' p+l using postorder traversal of T, connect any median with any vertex v. which has not yet sidered and is a descendant of that median. If g < p, found. Again, noncentral been con Step 8. Connect any vertex not yet considered to the nearest noncentral median which has less than r adjacent vertices. Connect all noncentral medians with the central median, v+ p+l'

11 It should be noted that the algorithm given above sequentially solves the following three problems (a) the construction of a minimum spanning tree, (b) the sequential allocation of p medians on this tree, and (c) the connection of exactly r vertices with every noncentral median. It is impossible to construct an exact polynomial algorithm for solving (a) and (c) because the corresponding problem of constructing a minimum spanning tree with bounded vertex degree is NP-complete [8, po 206]. 3. Estimation of Time Complexity and Accuracy of the Algorithms. We first estimate the maximum number of elementary operations required by each algorithm for solving any instance of our problem. For Algorithm 1, the time complexity is not polynomially bounded because it has been shown that the simplex method may take an exponential number of steps to reach an optimum [11]. The branch-and-bound procedure may also involve an exponential number of steps. Algorithm 2 can involve as many steps as the number of possible median sets, ( n ). Since this grows exponentially with n for fixed r, Algorithm 2 is also not polynomially bounded. We note, however, that these bounds apply to worst case behavior and that average case behavior may be much better.

12 We will now estimate the time complexity of Algorithm 3 step by step. Step 1 may be completed in 0(m log m) operations where m = I E. Since, in our case, we have a complete graph, m = 0(n ), then Step 1 has the estimation 0(n log n). Step 2 requires 0(m) operations. Step 3 consists of 0(p.c1) operations where cl is a constant and p = n+l Steps 4 and 5 in the long run require 0(p.n) operations. In fact, one application of Steps 4 and 5 will take 0(n) operations, if we construct a list of the vertices in which each vertex is assigned the weight of the subtree which includes that vertex and the corresponding value of A. Step 6 requires O(p.c2) operations where c2 is a constant. Steps 7 and 8 may be done in 0(n2) operations. Combining these estimates, we obtain the common estimation of 0(n2 log n). Algorithm 1 using the branch-and-bound procedure guarantees an optimal solution, but Algorithms 2 and 3 provide only approximate solutions. We next consider the accuracy of those algorithms. Let I be an instance of our problem and let a (I) = opt(I), the optimal solution value obtained using the exact algorithm 1. An instance of this problem will be defined as a set of given vertex locations on a predetermined size field. Let a2(I) and 3 (I) be the values of approximate solutions found using Algorithms 2 and 3o The problem in the remainder of this section is to determine the absolute performance ratios [8, p. 128], which are determined by the following formulas:

13 o2 (I) R2 = inf{r >: R2 (I) y=1(I) < r2 for all possible instances I}, (8) a (I) R = inf{r3 > 1: R3(I) 3= i(I) < r for all possible instances I}. We first present a lower bound estimate of the optimal solution, aO(I). For a problem with n vertices and p = (n/r+l) medians, the number of connections between the medians and all vertices may be caluclated by the following formula: n-p = n - n = nr (9) n-p = n - r+l r+l Let T be the set of all possible spanning trees for instance I. Let us denote the minimum edge length in all such trees by p. = in m{d(x., x )}, (10) n (xi,xj)~T C T J and let the maximum edge distance be P max {d(xi, x.)}. (11) IV(xi,xj)~TC T It is clear that nr l) - r+l Pmin (12) An optimal solution to the problem is not guaranteed by Algorithm 2, but the value of the solution may be bounded. At termination of the algorithm, no vertex may be substituted for another and lead to a lower value. We let (v, v,...,v*) be the median set in the optimal solution. p

14 Since none of these vertices which are not in the median set of the approximate solution may be substituted for a median in the approximate solution and lead to a lower total distance, we obtain E d(v, v.) + d(vk, v(k)) < d(v v) + d(v, v (13) Evi jEvi * 1 where vk C V (k) in the approximate problem. This inequality holds for every vertex vj. Vk(j) in the optimal solution. We take a sum of the left hand sides of (13) for vj for all i and j 1 to find i- Z7 1 C V{ Z d(v3, v) + d(v., v) +d(v- v1 )} i=l j 3v V j 3 v3 V. 1 kj ( 1 1 p 1 = r 2,(I) + Z Z d(v()-, V(k)) > r c2(I) + r.p, (14) where a2(I) is the value obtained in this instance by this approximate algorithm, n =p(r + 1) is assumed, and all arcs have a least unit lengths. For the right hand side of (13), we obtain: P l ( < d(vj, v + d vk( + d (k)) i=l 3 J 3 < Z Z ( Z d(Vi' v.) + Z d(v, vk )) + d(v-, v( )) - i=1 j j ' 1 j 1 k'+(j) k (j)) + d(vi, v (k))) < (r - l).o2(I) + cl(I) + r.p.dma """ z^ j- umax) (15)

15 where d = max d(v., v ). (14) and (15) give us the following. max 1 j V.iV. Proposition 2. The solution, a (I) obtained by Algorithm 2, is bounded by a2(I) < ol(I) + r p (d ma- 1) (16) where o (I) is the exact solution to (5). Proof. This follows directly from (14) and (15). The absolute performance ratio for Algorithm 2 may be obtained by: r p(d -1) R2 inf ( < 1 + a 21(I - nr r+1 min d - 1 1 + max (17) Pmin n using (16), (12), and p = r+ We note that for a field of dimensions |2 2 2 a by b, d < a + b, so R is bounded by a constant depending on max - the field size. We will now find the estimation for o3(I). Proposition 3. After allocating p medians to the set of vertices any subtree obtained from Algorithm 3 will include no more than: n a = 2- vertices, 2 where k = [log2(p + 1)j.

16 Proof. We will proceed by induction on p. For p = 1, then k = 1, O = -. Suppose that the proposition holds for p = g and consider the case, p = Z + 1. Two cases are possible: 1) Llog2 (Z + 1)J = Ltog2 ( + 2)J 2) jlog2 ( + 2) = Llog2 ( + 1)I + 1. Let k* = minf{} such that ILog2(R* + 1)j = log2 (A + 1)J. After having allocated * medians, we will have A* + 1 subtrees. It is clear that in Case 1 above there will exist at least one subtree with -n vertices where 2k k = log2 (Z + 1)J, and, in Case 2, all subtrees will be the same size, in n other words, every subtree will have no more than vertices, where 2 k = Llog2 (Z + l) + 1. It follows from Proposition 2 that the maximum path length in such a subtree will be no greater than ( 2k - 1) max, where k = l[og2 (p + 1). Let T1, T2,...,T be the sequence of subtrees of the minimum spanning tree T with corresponding roots vj, v.,....,v, adjacent with the central median v+* and such that w(v. ) > w(v. ) >-*> W(v. ). ~p~+l Jl - 2 - 2 - s Then, possibly, starting with some t, 2 < t < s, each of the subtrees TV, where t < Q < s, will not have a mediano Let S b = Z w(v. (18) Z=t 3J

17 It then follows from Proposition 3 that any subtree resulting from n-b Algorithm 3 will include no more than nk vertices, where k = log2 (p + 1)j. Without loss of generality, let p = 2m, where m > 1. (If not, p may be decreased to the nearest power of 2.) Then n-b n-b _(n-b) (rl) (19) 2 ol~g2(p+l)J n In order to obtain an upper bound estimate of ao3(I), it is necessary to investigate the most "unsuitable" instance of the problem for Algorithm 3. Obviously, this will occur when t = 2, that is, when all noncentral medians are allocated to a single tree, T1. It is clear that in this case each of the subtrees T2, T3,...,T will contain at most (r) vertices. 2*'.3' s n The most "unsuitable" structure for subtrees, T1, T2,o..,T, will be a tree, that contains only one leaf (i.e., a path). Let us denote by a31(I) the total distance from the vertices of subtree T1 to the corresponding nearest medians (Step 7 of Algorithm 3). Let a32(I) be the total distance from the vertices of subtrees T2, T3,...,T, to the corresponding nearest medians of subtree T (Step 8 of Algorithm 3). Then a3(I) = 31(I) + a32(I). (20) Let v. be one of the vertices of subtrees, T2, T3,...,Tk, and let v* be the nearest median in subtree T to vertex v.. Then, from the t 1 j triangle inequality in Euclidean space, it follows that: d(vi v*) < d(v v* ) + d(v v (21) j t J dp+l p+l' vt)'

18 T1 1 Figure 1. An example of the worst case tree for Algorithm 3. Stars are used to show the median allocations. The circle bounds the area of allocation of vertices of subtrees, T2, T3,, Tk.

19 From Step 5 of Algorithm 3, it follows that every noncentral median will be connected with no more than rb 1 = b(r +) vertices. This p n may be roughly estimated by b (n+l)1 < 2b(r+l) n - n Then 32 (I) < Vv. k T i U 3 i=2 d(v * ) + P 2b(r+l) d(v* J (vj, p+l E n p+l' t' t=l (22) Let us estimate the right hand side term in (22). It is clear that any of the subtrees T2, T3,..., Tk, has no more than (n-)(- ) vertices. Furthermore, the worst structure for any of these subtrees is a path. Using these facts, we have Vv. E J b'p *, max (n- b(r+l) d(v V +1) (n-b(r+) [1 + 2 +...+ - 1] n k T. U 1 i=2 n p pmax. (n-2)(r+l) b (n-b) (r+l (n-b)(r+l) 2 2n max' (n-b) (r+l) 2 n; 2 n (23) 2b(r+l). 2(r+l) (n-b) (r+l) n p+l' t)< - n n ma...x r+ = - n max r+l 2b.(r+l) n max b(n-b) (n+r+l) n (n + r+l) (n-b) (r l) 2(r+l)2 n ~ p mlax (24)

20 Using (23) and (24), we may estimate a32(I) by: r3 (I) < b(n-b) (r+l) 32 - 2max 2n b (n-b) (n+ r+l ) + P max (25) n We may also obtain an estimate for a31(I) by: 3(I) < P. ~* [1 + 2 +...+ (n-b)(r+l) 1] = 31 - r+l Omax n n r +1 (n-b)2(r+l) 2n m p max 2(n-b) 2n ~ max (26) Using (25) and (25), the following estimate of a3(I) is obtained. () (n- b) 2 (r+l) 3 (I < 2n max + b (n-b)(r+l) 2n max + b (n-b) (n+r+l) p n max n- +r 2n Pmax [(n-b:) (r+l) + b(r+l) + 2b(n+r+l) ] = ^il max n-b 2= max [nt'+n + 2bn 2n max + 2br + 2b] = n-b 2n Pmax [n(2b + r+l) + 2b(r+l)]. (27)

21 Using (27) and (12), we may find the ratio R3 by: Ra (I) R = inf o (I) } 1 (n-b)[n(2b+r+l) + 2b(r+l)]. (r+l) 2nn- r max min Pmax min (n-b)(r+l) [n(2b+r+l) + 2b(r+l)] 2 2n ~r (28) From (23) it follows that if we have b = 0, then: R < max R3 < min (r+l) n (r+l) 2nr Pmax (r+l)2 Pmin 2r min that is (29) Pmax R3 < 3- min mmn (r+1)2 2r Omax where ax is a constant that depends on the size of the field. min We observe that R2 and R3 are both bounded by constants when b is a constant but that R3 may be 0(n) if b = 0(n). This case is extremely unlikely for a field with equally distributed heliostats. It should also be noted that Algorithm 3 has the advantageof a polynomial bound in time complexity.

22 4. Computational Results. A set of randomly generated problems was used to test the algorithms. A FORTRAN code, SWTCHR, was written to perform Algorithm 2, and another FORTRAN code, MINST, was written for Algorithm 3. Both of these codes were compiled on the non-optimized standard FORTRAN-G compiler on The University of Michigan's Amdahl 470/V8 computer. All processing was also done on this machine. The linear program of Algorithm 1 was executed by the versatile MINOS package [14]. The linear program in (5) requires (n + 1)2 variables and more than (n + 1)2 rows. As n increases, the problem size becomes prohibitively large and finding a solution becomes extremely expensive. For this reason, tests of all three algorithms were limited to small n. The results in Table 1 are for problems in a 1000 meter by 1000 meter field in which n = 28 heliostats have randomly been placed uniformly in the field. For these examples, the microprocessor capacity was set at ten and three microprocessors were located within the field. The resulting linear program for these examples included 842 rows, 785 columns and 3921 nonzero elements. The CPU times given exclude input and solution output, Problems 2, 5, 6, 7 and 10 had some noninteger variables in their solution. These problems required additional processing through branch-and-bound to obtain an optimal all-integer result. The times reported for these problems do not include that additional processing. These problems were also solved by Algorithms 2 and 3 and the results were compared with the optimal linear programming solution, Algorithm 2 was started with a randomly chosen median allocation. The average accuracy of Algorithm 2 on the first set of problems was better than that of Algorithm 3 but its time requirement was greater.

23 Table 2 contains results for 100 random heliostat sites and for a capacity of 20 at each of 5 microprocessors. These problems are excessively large for an efficient linear program solution, hence the results are compared with the length of the minimum spanning tree instead of the linear program solution. Algorithm 2 again provides better average results but it requires consistently more time. It should be noted that the majority of calculation time is spent determining distances between pairs of heliostats. Since this operation only needs to be performed once, a combination of Algorithms 3 and 2 may prove quite useful in practice. In finding the minimum spanning tree in Algorithm 3, distances may be calculated and stored out of core. The solution from Algorithm 3 may be used as an initialization for Algorithm 2 and the distances may be recovered without additional computation. 5. Conclusion. The problem of minimizing cable connections in a solar power system has been presented. This task was modeled as a p-median problem with additional constraints and three algorithms were presented for its solution. Worst case analysis of the algorithms indicated that one heuristic method was polynomially bounded and that its absolute performance ratio was, in general, bounded by a constant. Computational results supported the relative efficiency of this polynomial heuristic algorithm.

24 Table 1 Solutions for n = 28 Heliostats. Linear Program Algorithm 2 Algorithm 3 % of % of Problem Itera- LP LP Number CPUs tions Value CPUs Value Opti. CPUs Value Opti. 1 34.7 606 6095.7.31 6306.4 103.16 6528.1 107 2 32.5 559 6129.5.32 6350.7 104.16 7642.3 125 3 38.3 680 5839.7.32 8301.0 144.15 7618.6 130 4 30.4 529 5992.3.32 6793.6 113.16 6931.1 116 5 37.7 629 5818.1.32 6716.8 115.18 8577.3 147 6 37.0 651 5426.7.32 6005.3 111.16 7733.1 142 7 40.8 754 5894.4.31 6656.1 113.14 7925.4 134 8 30.0 519 5230.3.31 6346.4 121.14 5964.6 114 9 45.0 765 5691.5.31 7935.5 139.14 8424.3 148 10 32.9 487 5711.5.31 6382.0 112.15 7348.8 129 Average 35.9 618 5783.0.32 6788.4 118.15 7469.4 129

25 Table 2 Solutions for n = 100 Heliostats Minimal Spanning Algorithm 2 Multiple Algorithm 3 Multiple Problem Tree of of Number Value CPUs Value MST CPUs Value MST Number.Value. CP.s. Value M.T C V MST 1 2 3 4 5 6 7 8 9 10 6961.2 6998.3 7051.6 6635.9 7017.0 6493.7 6892.0 6641.3 6993.1 6759.1 10.5 10.2 10.2 10.3 10.3 10.3 10.4 10.3 10.4 10.3 22516.5 19669.2 23107.3 22783.3 23285.5 20549.5 18542.7 22196.7 25149.0 18329.6 3.23 2.81 3.28 3.43 3.32 3.16 2.69 3.34 3.60 2.71 4.2 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 4.1 27679.8 20321.9 23310.0 20603.0 25748.7 25649.0 25773.9 24504.6 29803.8 20978.2 I 3.98 2.90 3.30 3.10 3.67 3.95 3.74 3.69 4.26 3.10 Average 6844.6 10.3 21612.9 3.16 4.1 24437.3 3.57

26 References 1. Aho, A. V., Hopcroft, T. E. and Ullman, J. D., The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, 1974. 2. Ahromenko, G. E. et. al, "The Control of the Field of the Heliostats of the Solar Power Plants," Heliotechnics (USSR), Vol. 4, (1980), pp. 16-22. 3. Bignon, N. J., "Power from the Sun by Termodynamics: French Tower Type Projects," in Vezitoglu, T. N. ed., Solar Energy: International Progress, Proceedings of the International Symposium Workshop on Solar Energy, 16-22 June, 1978, Cairo, Egypt, Vol. 3, Pergamon Press, New York, 1980, pp. 1329-1337. 4. Carden, P. O.,"Steering a Field of Mirrors Using a Shared Computer-based Controller," Solar Energy, Vol. 20 (1978), pp. 343-355. 5. Christofides, N., Graph Theory, An Algorithmic Approach, Academic Press, 1977. 6. Enger, R. C. and Weichel, H., "Solar Electric Generating System Resource Requirements," Solar Energy, Vol. 23 (1979), pp. 255-261. 7. Francia, C., "Pilot Plants of Solar Steam Generating Stations," Solar Energy, Vol. 12 (1968), pp. 51-64. 8. Garey, M. R., and Johnson, D. S., Computer and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979. 9. Goldman, A. J., "Optimal Center Location in Simple Networks," Transportation Science, Vol. 5 (1971), pp. 212-221. 10. Holl, R. J., "A Central Receiver Solar Power System for Remote Locations," in Veziroglu,T. N. ed., Solar Energy: International Progress Proceedings of the International Symposium Workshop on Solar Energy, 16-22 June, 1978, Cairo, Egypt, Vol. 3, Pergamon Press, New York, 1980, pp. 1408-1425. 11. Klee, V. and Multy, G. J., "How Good is the Simplex Algorithm?" in Shisha, 0., ed., Inequalities III, Academic Press, New York, 1972, pp. 159-175. 12. Lin, S., "Computer Solution of the Travelling Salesman Problems," Bell System Technical Journal, Vol. 44 (1965), pp. 2245-2269. 13. Lipps, F. W., and Vant-Hull, L. L., "A Cellwise Method for the Optimization of Large Central Receiver Systems," Solar Energy, Vol. 20 (1978), pp. 505-516.

27 14. Murtagh, B. A. and M. A. Saunders. MINOS User's Guide, Systems Optimization Laboratory, Technical Report 77-9, Stanford, 1977. 15. Revelle, C. S. and Swain, R. W. "Central Facilities Location," Geographical Analysis, Vol. 2 (1970), pp. 30-42. 16. Sandia National Labs, User's Manual for Delson 2: A Comuter Code for Calculating the Optical Performance and Optimal System Design., Report No. 8237, Albuquerque, 1981. 17. Smith, 0. T. M. and Smith, P. S. "A Helioelectric Farm," in Veziroglu, T. N. ed. Solar Energy: International Progress, Proceedings of the International Symposium Workshop on Solar Energy, 16-22 June, 1978, Cairo, Egypt, Vol. 3, Pergamon Press, New York, 1980, pp. 1368-1407. 18. Teitz, M. B. and Bart, P., "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph," Operations Research, Vol. 16 (1968), pp. 955-961.

UNIVERSITY OF MICHIGAN 3 115 03994 11297 II 3 9015 03994 8297