APPLICATIONS OF LINEAR INTEGER PROGRAMMI4NG TO PROBLEMS OF LAND USE ALLOCATION R. L. Patterson School of Natural Resources The University of Michigan June 1972 Sea Grant Technical Report 31 MICHU-SG-72-213 THE UNIVERSITY OF MICHIGAN SEA GRANT PROGRAM

The University of Michigan Sea Grant Program is a part of the National Sea Grant Program, which is maintained by the National Oceanic and Atmospheric Administration of the US Department of Commerce.

CONTENTS Page Constrained Optimization and Land Use.............. 1 A Simplified Land Use Assignment Problem. 5 A Multiple Land Use Assignment Problem............. 12 Difficulties in Formulating Linear Objective Functions.22 Difficulties in Specifying Cell Sizes........... 23 A Modified Site Assignment Problem............. 25 Applications of Mixed Integer Programming. 28 Goals Programming.. 28 References..................... 36

CONSTRAINED OPTIMIZATION AND LAND USE Constraints in the designation of terrain for uses can appear in the form of budget limitations for development, rules, and regulations which limit the uses of sites, minimum space needs for certain types of uses such as parks and housing, locational requirements for certain land uses, physical-chemical-biological dynamics that must be preserved, standards of site suitability for particular uses, certain measures of user satisfaction, regulations on ownership or controllership, standards on environmental quality, and total amount of land available. From the variety of ways and means of limiting land use, it is obvious that no single model is adequate to cover all combinations of possible constraints. Optimization implies the existence of a preferred pattern or patterns of land use selected on the basis of a comparison of alternatives from a set of possibilities. Criteria for optimization may be expressed in objective terms such as dollar costs, number of users, dollar income, amounts of wastes discharged, user-miles or user-days, site productivity, or number of user demands that are satisfied. Subjective criteria may also be used. For example, a quantified measure of site "suitability" consisting of a weighted linear numerical combination of physical and aesthetic characteristics is subjective. Whenever one individual states a preferred choice between two uses on a given site, he is exercising a subjective but nonquantified criterion. The use of quantitative criteria forces one to be specific about those factors that dominate his preference behavior. Much more disagreement is to be expected over the basis for

rating one plan or site use over another when the criteria are subjective rather than objective. Constrained optimization means a choice of the most preferred pattern of site uses from a limited set of alternatives. Limitations can occur for any of the reasons just mentioned, the most basic of which is the limited supply of land. Constraints are not independent of criteria. For example, a short supply of land drives up the price that certain groups are willing to pay for user rights. An "optimized" allocation of uses to sites is a decision, choice, or recommendation, whether hypothetical or actual, that corresponds to selecting the top-ranked alternative from those available under the given limitations. A form of constrained optimization is practiced in matters of land use decision making, although not with the aid of computers and mathematics. Developers or other entrepreneurs, public and private, determine their own preferences for land use, which cover a limited set of sites. Each acts so as to gain his maximum advantage so that the set of land use decisions is optimized from the collective points of view of this set of users. Regulatory agencies enter the picture by placing limitations on permissible alternatives because conflicts arise among competing users, or between competing users and other potential users (public or private). Conflicts arise over differences in criteria adopted by user groups, the most publicized example being economics or job versus preservation of resources or "ecology." Conflicts also arise because one user group uses a site for a purpose that interferes with the purpose of another user group on the same site or a different site. Expression of user preferences may exist in the form

of requests for zoning variances, public opinion stated through hearings, requests for permits to undertake development, or outright development of a site. Development always occurs over time in a sequential pattern, so that no single agency can identify at any particular time the set of interested users, their set of preferred alternatives, or their criteria for choice. Therefore, planning or regulatory agencies cannot "optimize" land use decisions for other independent users. They can advise or present suggested plans according to a set of criteria, or they can act as arbitrators by setting constraints on permissible land use decisions. It is very difficult, if not impossible, in actual practice for an agency to measure the degree to which a pattern of existing land uses is optimum whenever several independent user groups are involved in the decisions. It is sometimes possible for a single user or a single agency acting on behalf of a group of users to optimize land use "plans" (on a limited scale). A realistic example occurs in the case of a state agency whose task it is to purchase and develop acreages for public recreation. A set of possible sites are first selected on the basis of a "site suitability" analysis. Next, the sites are ranked according to their natural and cultural features and according to their accessibility to the region's population. Finally, a subset of sites must be selected, each with a set of acreages such that budget constraints are met and some measure of user satisfaction is maximized. The resulting solution can be called an "openspace plan." It is a set of hypothetical decisions that would be optimum if executed simultaneously under the conditions assumed in the statement of

the problem. It should be noted that a "site suitability" analysis may precede the site selection process in order to provide an information base for the preliminary selection process. Site suitability analyses may consider many factors, and the results may be displayed in graphical format, bdut this analysis does not in itself represent an optimized land use plan. A second type of "optimized" land use planning arises from the need to control undesirable consequences of land uses. As opposed to the previous case, where a set of hypothetical decisions are made to purchase or otherwise develop certain sites (so as to maximize user satisfaction or minimize development costs), the present problem is to limit undesirable side effects of land use. Waste discharges either in total amount of distribution, disruption of plant and animal communities, or a lowering of aesthetic values are examples of undesirable effects that may need to be controlled. This can be accomplished in part by zoning regulations on land use or by laws regulating waste discharges. In the case of zoning, a public agency may act to protect its constituency against excessive waste discharges or other "infringements" by developing a zoning ordinance that maximizes user access to land use and development subject to standards of "environmental protection." An important input to this type of plan is the "site capacity analysis," which is an analysis of the degree of deterioration that a site undergoes if subjected to different uses. Constraints occur in either hypothetical or real decision problems regarding the use of land whenever an interested party is not free to attain his preferred alternative. When several such constraints occur and

several decisions are to be made, constrained optimization implies a procedure for finding a solution that is superior to most others which meet the limitations imposed by the constraints. Most constrained optimization problems in land use decisions involve methods that are not based upon a mathematical model. Persons involved can state their preferences and value judgments without committing themselves to numbers. The disadvantage is that users may overlook a feasible alternative that they would have preferred had they discovered it. The other main advantage to using a mathematical model of land use decision making programmed for exercise on a computer is the vast amount of bookkeeping that can be done and alternatives that can be quickly and systematically checked. A SIMPLIFIED LAND USE ASSIGIMiENT PROBLEM A number of parcels of land are specified, each of which is capable of sustaining any one of several alternative uses. The problem is to assign exactly one use to each parcel in such a way that some measure of user satisfaction is maximized. There may be side conditions to be satisfied such as a minimum, maximum, or exact limit on the number of sites that may be assigned any particular use. This problem is illustrated by the following example. Mission Peninsula, *in Michigan, divides the lower part of Grand Traverse Bay into east and west arms. By superimposing a square grid on the peninsula, as shown in Figure 1, the land area is subdivided into

S~~~~ i ~~~~~~~~~~~35 _~~~~ /1 21 L 4d s 6 7 t___x~~8' 2 7( 31 /1 l2! 38X 34 9 4l 3 4j 1 1 16 1 7 1 81 / ~ ~ 20 51 2 2 5 26 7 2 28 29 1 30 3 1 132 3 34 35'136 37 38 393 40> 4 41 4 3 3 45 6 4 48 49 3 0 r1 u2 1 53 u 14 P 5

parcels, each of which is 1 sq mi in size. The grid lines follow the official section lines that define the land units by township and range designation. For purposes of illustration, each of 55 cells are assumed to require an assignment of a single "land use." That is, any grid cell that overlaps any part of the peninsula is to be assigned exactly one use uniformly applied over the land within that cell. Six different uses are defined as recreational (R), residential (RS), industrial (I), recreational-residential (R-RS), recreational-industrial (R-I), and residentialindustrial (RS-I). The "value" of each type of land use in a particular cell is assumed to be specified by a single number. In Table 1 a value for each use is specified for each of the 55 parcels. It is also assumed that the following land use requirements are given (Table 2). Each parcel is to be assigned to exactly one use in such a way that the total value is maximized. That is, the sum of the individual contributions by each parcel to total "value" is to be maximized. The statement of the problem is summarized in Table 3. The identification of the parcels by numbers from 1 through 55 is given in Figure 1 and the solution is given in Figure 2. The meaning of the "solution" is that no other assignment of land uses to parcels subject to the specified requirements gives a higher cumulative value, obtained by adding the values contributed by each parcel with its assigned use. The Assignment Model The problem as stated above fits the standard format of the "assignment" problem, which is an integrer linear program given by equations 1-4.

Table 1. Land Use Type Cost and Requirements R RS I R-RS R-T RS-I Parcel # DEST... 1 DEST...2 DEST...3 DEST... 4 DEST...5 DEST...6 1 -100 -90 -80 -95 -90 -85 2 -100 -90 -80 -95 -90 -85 3 -100 -90 -80 -95 -90 -85 4 -100 -90 -80 -95 -90 -85 5 -100 -90 -80 -95 -90 -85 6 -50 -90 -80 -70 -65 -85 7 -100 -90 -80 -95 -90 -85 8 -100 -80 -80 -90 -90 -80 9 -50 -90 -80 -70 -65 -85 10 -100 -90 -80 -95 -90 -85 11 -100 -90 -80 -95 -90 -85 12 -100 -90 -80 -95 -90 -85 13 -50 -90 -80 -70 -65 -85 14 -100 -90 -80 -95 -90 -85 15 -100 -90 -80 -95 -90 -85 16 -100 -90 -80 -95 -90 -85 17 -50 -90 -60 -70 -55 -75 18 -100 -80 -60 -90 -80 -70 19 -50 -80 -60 -65 -55 -70 20 -50 -80 -60 -65 -55 -70 21 -50 -80 -60 -65 -55 -70 22 -100 -80 -60 -90 -80 -70 23 -100 -90 -80 -95 -90 -85 24 -100 -90 -80 -95 -90 -85 25 -100 -90 -60 -95 -80 -75

Table 1. Continued R RS I R-RS R-I RS-I Parcel # DEST...1 DEST... 2 DEST... 3 DEST...4 DEST...5 DEST...6 26 -50 -80 -60 -65 -55 -70 27 -100 -80 -60 -90 -80 -70 28 -100 -90 -80 -95 -90 -85 29 -100 -90 -80 -95 -90 -85 30 -100 -90 -60 -95 -80 -75 31 -100 -80 -60 -90 -80 -70 32 -100 -90 -80 -95 -90 -85 33 -100 -60 -60 -80 -80 -60 34 -100 -60 -60 -80 -80 -60 35 -100 -80 -60 -90 -80 -70 36 -100 -80 -60 -90 -80 -70 37 -100 -80 -60 -90 -80 -70 38 -100 -60 -60 -80 -80 -60 39 -100 -80 -60 -90 -80 -70 40 -50 -80 -60 -65 -55 -70 41 -100 -80 -60 -90 -80 -70 42 -100 -90 -60 -95 -80 -75 43 -100 -90 -60 -95 -80 -75 44 -100 -90 -60 -95 -80 -75 45 -100 -100 -60 -100 -80 -80 46 -100 -100 -60 -100 -80 -80 47 -100 -90 -60 -95 -80 -75 48 -100 -90 -80 -95 -90 -85 49 -100 -100 -80 -100 -90 -90 50 -100 -90 -80 -95 -90 -85 51 -100 -90 -80 -95 -90 -85 52 -100 -90 -80 -95 -90 -85 53 -100 -90 -80 -95 -90 -85 54 -100 -90 -100 -95 -100 -95 55 -100 -90 -100 -95 -100 -95 55 -100 -90 -100 -95 -100 -95~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

10 Table 2. hypothetical Land Use Requirements Use R RS I R-RS R-I RS-I Parcels Required 19 4 5 19 4 4 Table 3. Maximize Total Value of Parcel —Use Assignment LAND USE TYPE Amount Parcel # R RS I R-RS R-I RS-I Available 1 1 2 1 Value (Table 1) 54 1 55 1 19 4 5 19 4 4 55 # Parcels Required Total

11 R-R R-RS R-R R-RS I -RS R I RS R-RS - RS RS-I R RS R R RS R R I RS- I RS R R \ RS-I R R-RS R- RS R- RS R R-RS R R R R R RS R R- S R-RS R-RS -RS R- I RS -J R-I R-I I I IFigure 2. Solution Assignment

12 M N max xijvij, i=l j=l where M = feasible sites and N = needs, subject to Lx. =1 (2) j=l j=l (i = 1,..., M) E x.. = r (3) (j = 1,..., N) x > 0 (4) ii - This problem can be solved by a variety of algorithms. In particular, the Graves-Thrall algorithm (Spivey and Thrall, 1970) was used to solve the preceding problem, in which M = 55 and N = 6. The algorithm coded as outlined by Hall et al. (1971) and stored under the Michigan Terminal System (MTS) is an efficient computational tool. A problem of this magnitude can be solved at a cost of $1-2. A MULTIPLE LAND USE ASSIGNMENT PROBLEM If any parcel is to be permitted one or more land uses simultaneously, and if the amount of usable land varies with the parcel, then the model using equations 1-4 is inadequate. For example, Table 4 shows a set of

Table 4. Percentages of Each Available Land Use Type Percent Parcel R RS I R-RS R-I RS-I Available 1 6 6 0 8 5 3 10 2 64 40 72 60 52 80 3 * 3 0 4 3 2 05 4 * * * * * 20 5 86 52 9 69 47 31 90 6 90 56 20 73 55 38 100 7 18 14 19 17 16 20 8 29 18 32 27 23 35 9 60 0 80 50 30 100 10 * * * * * * 50 11 12 0 16 10 6 20 12 36 0 48 30 18 60 13 60 0 80 50 30 100 14 * * * * * * 35 15 * 2 0 4 2 1 05 16 78 46 0 62 39 23 80 17 60 0 40 50 30 100 18 12 0 16 10 6 20 19 14 16 35 28 23 40 20 90 52 10 71 50 31 100 21 60 0 80 50 30 100 22 15 0 20 13 8 25 23 * * * * * 25 24 38 36 39 38 37 40 25 53 28 23 40 38 25 75

Table 4. Continued Percent Parcel R RS I R-RS R- I RS-I Available 26 * 64 10 82 55 37 100 27 * 42 0 56 35 21 20 28 *05 29 * * * * * * 05 29 ~k;t; ~ k 3e ~ e 05 30 * 14 4 17 12 9 20 31 90 51 0 71 45 26 95 32 10 32 * * * * * * 10 33 * 15 0 20 13 8 25 34 * 14 12 14 14 13 15 35 * 12 0 16 10 6 20 36 * 54 0 72 45 27 90 37 * 48 0 64 40 24 80 38 05 38 * * * * * * 05 39 * 54 16 67 48 35 80 40 * 68 20 84 60 44 100 41 * 27 0 36 23 14 45 42 * 12 0 16 10 6 20 43 * 54 0 72 45 27 90 44 * 24 0 32 20 12 40 45 44* * * * * * 05 46 * 44 18 52 39 31 60 47 * 24 0 32 20 12 40 48 * 12 0 16 10 60 20 49 * 52 32 70 56 46 80

Table 4. Continued Percent Parcel R PS I R-RS R-I RS-I Available 50 * 34 10 42 30 22 50 51 * 48 0 64 40 24 80 52 * 48 8 61 42 28 75 53 * 36 0 48 30 18 60 54 * 87 76 91 86 82 95 55 * 10 9 10 10 9 10

16 percentages of area available in each parcel for each land use together with the total area percentage available in each parcel for assignment. Note that the acreages available for each use in a parcel are upper limits rather than exact requirements, and therefore can sum to more than the total percentage of land available in the cell. (Percentages are converted to acreages by multiplying each percentage by 640.) An asterisk means that it is permissible to assign a particular parcel to a given use in its entirety. Interpreting the entries in Table 1 as value gained for each additional percentage of land area assigned to a given use, and imposing percentage requirements shown in Table 5, acres required = percentage required(640), one can define the problem of assigning mixes of land uses to each parcel in such a way that total cumulative value is maximized, the availability constraints on each parcel are not violated, and the requirements of the total amount of land assigned to each use are satisfied. The optimum Table 5. Hypothetical Land Use Requirements Land Use Type R RS I R-RS R-I RS-I Total % Required 463 463 463 462 462 462

17 assignment is presented in Table 6, while Figure 3 shows a possible placement of the optimum assignments. The format of this problem matches that of the standard transportation or distribution problem well known in linear programming literature: M N max x. ijvi.... (5) 1J 1J i=l j=1 subject to N E_ ij i(6) j=l (i = 1,..., M) M i=i <j = 1,..., N) O < x.. < c. (8) 1J - 1J (i = 1,..., M) (j = 1,..., N) Equation 6 states the total amount of land available for assignment in each parcel, equation 7 states the overall requirements for each land use type, and equation 8 states the limitations that may exist on assigning particular uses to particular parcels.

Table 6. Optimum Assignment of Uses to Parcels 463 463 463 462 462 462 Rec Res Ind Rec Res Rec Ind Res Ind % Land Avail. Cell # % Cell Acres % Cell Acres % Cell Acres % Cell Acres % Cell Acres % Cell Acres in Cell Acres 1 2 12.8 5 32 3 19.2 10 64 2 40 256 40 256 80 512 3 3 19.2 2 12.8 5 32 4 15 96 5 32 20 128 5 9 57.6 3 19.2 47 300.8 31 198.4 90 576 6 1 i 42 268.8 20 128 38 243.2 100 640 7 14 89.6 6 38.4 20 128 8 18 115.2 17 108.8 35 224 9 60 384 10 64 30 192 100 640 10 50 320 50 320 11 4 2.56 10 64 6 38.4 20 128 12 12 76.8 30 192 18 115.2 60 384 13 60 384 10 64 30 192 100 640 14 35 224 35 224 15 2 12.8 2 12.8 1 6.4 5 32 16 18 115.2 39 249.6 23 147.2 80 512 17 60 384 10 64 30 192 100 640 18 10 64 10 64 20 128

Table 6. Continued %Land Rec Res Ind Rec Res Rec Ind Res Ind Avail Avail. Cell # % Cell Acres % Cell Acres % Cell Acres % Cell Acres % Cell Acres % Cell Acres in Cell Acres 19 1 6.4 16 102.4 23 147.2 40 256 20 52 332.8 10 64 7 44.8 31 198.4 100 640 21 60 384 10 64 30 192 100 640 22 5 32 20 128 25 160 23 25 160 25 160 24 36 230.4 4 25.6 40 256 25 19 121.6 16 102.4 40 256 75 480 26 63 403.2 37 236.8 100 640 27 16 102.4 4 25.6 20 128 28 5 32 5 32 29 5 32 5 32 30 3 19.2 17 108.8 20 128 31 90 576 5 32 95 608 32 10 64 10 64 33 25 160 25 160 34 15 96 15 96 35 4 25.6 16 102.4 20 128 36 90 576 90 576 37 80 512 80 512 38 5 32 5 32 39 41 262.4 39 249.6 80 512 40 36 230.4 20 128 44 281.6 100 640 41 22 140.8 23 147.2 45 288

Table 6. Continued Land Rec Res Ind Rec Res Rec Ind Res Ind Aail Avail.. Cell # % Cell Acres % Cell Acres % Cell Acres D Cell Acres % Cell Acres % Cell Acres in Cell Acres 42 4 25.6 16 102.4 20 128 43 18 115.2 72 460.8 90 576 44 8 51.2 32 204.8 40 256 45 5 32 5 32 46 8 51.2 52 332.8 60 384 47 8 51.2 32 204.8 40 256 48 10 64 10 64 20 128 49 32 204.8 2 12.8 46 294.4 80 512 50 10 64 30 192 10 64 50 320 51 21 134.4 40 256 19 121.6 80 512 52 8 51.2 25 160 42 268.8 75 480 53 30 192 30 192 60 384 54 76 486.4 19 121.6 95 608 55 9 57.6 1 6.4 10 64 Total 463 2963.2 463 2963.2 463 2963.2 462 2956.8 462 2956.8 462 2956.8 2775 Total Acres Available = 17,760 Total % in Cells = 2,775

21 R- I RI R 1 asF RS-l-I 1RS RI FgRS-e3HyohilOp ds R-RS RSIl RSI IR IR/ RS-I RS R-RS a c, R~~~~~~~~~~~ R-l I Y RS-I RS R-RS RS RS- I R- I R-R F 3 Figure 3. H~ypothetical Optimized Land Use Pattern

22 The two numerical examples given illustrate the type of answers obtained for the "land use assignment" problem as defined. One finds the term "land use planning" frequently used, but it is difficult to determine what the user really intends to convey by the words. Similarly, it is not clear that the land use assignment problems as defined here can be interpreted in a practical sense so that various constraints are realistic and the criterion for optimization is objective. As interpreted here, Zand use means activity by man upon the surface of terrain which may involve a reconfiguration of the terrain or may result in subsurface changes to soil, water balances, and mineral inventories, or may result in changes to the plant and animal populations living on and above the surface. Planning as used here means a systematic analysis of the impacts of human activities upon terrain, an assessment of future user demands, and a recommendation of permissible terrain uses. DIFFICULTIES IN FORMULATING LINEAR OBJECTIVE FUNCTIONS Objective functions (1) and (5) assume that the degree of preference of one assignment of uses to sites is the sum of the individual "values" derived from assigning uses to each site separately. No value is placed upon the pattern per se. This assumption is valid in cases where an objective criterion such as monetary cost is used and for which the overall pattern effect is nonexistent. For example, the case of choosing a subset of preselected recreational sites so as to minimize development cost would not involve the pattern effect. Pattern effects introduce nonlinearities

23 into the objective function. If one uses subjective values in the criterion for numerically ranking alternative assignments, the same difficulty arises. If two sites are each rated a value of two when assigned a given use, is this particular alternative equivalent to assigning the same use to a third site, which receives a rating of four? In the objective functions (1) and (5) the answer is assumed to be affirmative, which implies no pattern effect. The existence of a pattern effect means that sites must be considered in groups of two or more as well as individually. Various possibilities occur for incorporating pattern effects into a linear objective function, one of which is to enlarge the size of some or all of the sites, thereby reducing the total number of sites. The disadvantage of this procedure is that the ratings assigned to particular uses on a given site will not apply over the entire site. Another way to account for pattern effects is to remove any uses or combinations of uses that create pattern difficulties. If zoning a given site "industrial" lowers the value of an adjacent site zoned "residential," then one or the other uses can be removed from the problem. An alternative is to define an industrial use to include a buffer zone so that devaluation of adjacent sites does not arise. DIFFICULTIES IN SPECIFYING CELL SIZES The smaller the land unit area, the more homogeneous its characteristics and hence the more uniform its numerical description. Steinitz

24 (1970) has found 2.5 acres to represent an adequate balance between numbers of cells and uniformity of cell characteristics when performing suitability and capability analyses over an area of several thousand acres. In the integer programming model examples just given, each cell requires one equation so that doubling cell size reduces the number of equations by 50 percent. The limitations of the code described by Hall et al. (1971) restrict the product of the number of cells and the number of uses to be less than 70,000 for a "capacitated" problem and less than 90,000 for an "uncapacitated" problem. From the viewpoint of computational efficiency, it would be preferable to reduce the number of equations and hence increase cell size. Another difficulty created by small cell sizes is that uses tend to be sprinkled over an area in a "salt and pepper" fashion, more so than in the case of larger cell sizes. This tendency focuses upon a basic element of unrealism in the two models specified, which place no minimum requirement on the size of local areas assigned to a single use. For example, a shopping center that requires 1,000 acres cannot be designed on 10 separate locations of 100 acres each. This shows the capacitated transportation and assignment models are inadequate to solve a Zocation-acZocation problem which implies decision making on where to reserve a number of land parcels, each of a specified size, for specific uses in an "optimal" manner, subject to possible land use constraints of the types previously listed. In the location-allocation problem, the area required for each of a fixed number of uses is specified in advance. The possible sites for each use are identified in advance, and the problem is to locate the uses

25 in an optimal manner. The problem of a "patchwork quilt" type of assignment pattern never arises. The sizes of the cells do not affect the area distribution of the uses. A MODIFIED SITE ASSIGNMENT PROBLEM The assignment model specified by (1) through (4) is more realistically applied when sites are redefined as "feasible" sites for specific land use needs such as shopping centers, industrial parks, recreational parks, or residential subdivisions. Sites are now variable in area and shape and are located specifically in terms of identified "needs." The site "use" now becomes a need which is defined in terms of cost, required land characteristics, area, and other identifying features. A1 set of needs, N, is defined, which leads to a selection of feasible sites, M, upon which to satisfy some or all of the needs. The parameters of the problem are summarized in Table 7. The assignment problem is easily solved using the code defined by Hall et al. (1971). It makes no difference whether M > N or F1 < N as far as the numerical solution is concerned. The algorithm simply defines fictitious feasible sites or needs as required to "balance" the problem. The feasible sites can be chosen with the aid of site suitability and site capacity maps developed during or preceding the site feasibility study. The algorithm assigns needs to feasible sites in such a way that total cost is minimized. If the total minimum cost exceeds a budget limitation, then needs can be reduced until budget constraints are met.

26 Note that the assignment can be made using dollar costs and remade using some other objective criterion such as user convenience, number of users, or damage to the environment. The solutions can be compared before a final choice is determined. If a given site is infeasible for a specific need, the corresponding cost is assigned a high value so that the need is never assigned to that site. Even if feasible sites exceed the number of needs, there may still exist competition between needs for a particular set of sites. If the number of needs and feasible sites is sufficiently small, a computer analysis is unnecessary. In a sense there always exists "competition" of a proposed need with the existing use of a site. The "loss" associated with converting the site from one use to another can be considered when defining the cost coefficients shown in Table 7. It is important to note that two "needs" may be two different acreage requirements for the same basic use, for example, a large residential subdivision and a small residential subdivision. If the costs are nonlinear with the size of the site required, the appropriate costs can be stated without difficulty in the cost table. Needs arise in a sequential fashion. If needs can be anticipated to a time horizon of T years, then all anticipated needs can be simultaneously considered over this period. The longer the time horizon for anticipating needs, the more difficult it is to propose alternative sites since the uses of adjacent lands may have changed before a decision can be implemented, thus making the "costs" unrealistic.

27 Table 7. Tableau for Assignment Problem Needs Feasible Amount Sites 1 2....... N Available 1 C11 C C1N 1 11 12....... 1N 2 1 C21 C22 1 (Cost) M CM11 Amount Required 1 1 1

28 APPLICATIONS OF MIXED INTEGER PROGRAMMING Mixed integer programming applications are introduced by IBM (1972). Conditions in land use decision making which lead to mixed integer programming problems are (1) either use A or use B, but not both, is required on a given site; (2) a given development is to be carried out on a scale of either A, B, or C acres; (3) several recreational sites are to be located so as to satisfy user demands, and each site has an overhead cost and a variable operating cost. Mixed integer programming requires algorithms and codes different from integer programming and is not pursued here. GOALS PROGRAMMING "Goals programming" is defined by Spivey (1970) as a linear program, a special case of which is described and illustrated in this report. The problem considered here is the following: A manager has M geographic zones under his control, to each of which he must budget N different resources. He has established "goals" based upon past performance and future expectations which specify the amount of each resource he prefers to assign to each zone. There are penalties for overbudgeting or underbudgeting resources in any given zone which may differ by zone and type of resource.

29 There also exist minimum resource requirements necessary for each zone that are less than those specified in the goals. There may exist, in addition, upper limits on the amount of each resource available for distribution over all zones. As in the case of a total dollar budget that can be broken down by zone and by resources within zones, there may exist an overall budget limit. Finally, there may exist limitations called "zone capacities" that place restrictions on "total equivalent resources" that can be assigned to each zone. The problem is to allocate resources to zones in such a way that the total cost of deviation from the goals is minimized subject to the given limitations. The problem is formulated as a linear program by first defining the following quantities. Let rl.rl N R1 R: R=.=.' =1[1(9) _i JI x 1 MxN where r.. = preferred level of resource j established for zone i (j = 1, 2,..., N) (i= 1, 2,..., M). L =, (10) Nx 1

30 where. = minimum required amount of resource i over all zones (i = 1,..., N). L (11) N. N x 1 where Q. = maximum permissible amount of resource i assignable to all zones. 0- 1N1 o = i = =, (12) MxN M x N::MN MxN Mxl 1 where 0 = coefficient used to convert resource j in zone i into a standard or equivalent unit, for example, number of vehicles -+ dollars or - number of vehicles + square feet of land surface. Ul 1 - - - - U1N 1 U = [1] =: (13) u1 - L UMN M MxN Mx 1

31 where u.. = units of resource j overbudgeted for iJ zone i (i = 1,..., M) (j = 1,..., N). V = I = [Y], (14) vM1. VMN VM where v. - units of resource j underbudgeted in zone i (j = 1,..., N) (i = 1,..., M). C _ - - C C C=: = (15) CMl - - - - CMN CM MxN Mx 1 where ci = unit cost of overbudgeting resource j in zone i converted to a common or equivalent unit. C * C = M= [, 1 (16) ml MN M MxN Mxl 1 where c..* = unit cost of underbudgeting resource j in zone i converted to a common or equivalent unit.

32 The problem is to minimize M M U. i i+ j VC.*i (17) i=l i=l subject to U T T > LT R T.T (18) i= i i=l i=l (minimum requirements on resources) M M M U uT' T T R i - Vi < L - i i=l i=l i=l (maximum permissible assignments of resources) N M (rij + uij + vj)di <- (20) j=l i=1 (overall budget unit) where d.. = unit budget equivalent for resource j J on zone i. on zone i.

33 T 1 (01 - V1) < al - 0 R T (21) OM(UM -VM) < aM OM T U,V > 0, (22) (limitations on total equivalent value on resources assignable to each zone) where a. = maximum equivalent value assignable to zone i. In certain problems some subset of restrictions (18) - (22) may be missing. Examp le Problem A university planner requires acreage for four uses (resources) which are (1) open space, (2) recreation, (3) parking, and (4) housing, each of which must be distributed over three campuses. His goal is specified as follows: Open Space Recreation Parks Parking Housing Zone (sq. ft.) (# people served) (# Vehicles) (# Family Units) 1 500,000 500 100 100 R = 2 500,000 500 100 100 3 300,000 500 75 50

34 The common unit for allocation of acreage is square feet, and conversion units are specified by o.s. rec. pks. park. hous. 1 1 1,000 150 1,000 0 = 2 1 1,000 150 1,000 3 1 2,000 150 1,000 It is mandatory that the following minimum requirements be met for open space, recreational parks, vehicle parking, and family housing: 1,000,000 (sq. feet) 1,000 (people) L = 2 ]200 (vehicles) 100 (family units) The zones have maxima 1,500,000 (zone 1), 1,000,000 (zone 2), and 1,000,000 (zone 3) sq ft of area available for assignment. The planned goal will not be met immediately, so a relative cost of over- and underbudgeting acreage for use is specified: open space rec. parking housing 1 1 2 5 10,C = 2 1 2 5 10 (over- 3 1 2 20 50 budget)

35 open space rec. parking housin 1 1 2 10 20 C* = 2 1 2 10 20 (underbudget) 3 1 3 5 4 When programmed for solution using a simplex code, there are 24 decision variables (12 u..'s and 12 v..'s). As explained by Hall (1971), u.. and 1J 1J 1J v.. (for all i,j) cannot both be simultaneously strictly positive. That is, one cannot simultaneously overbudget and underbudget acreage to the same use in the same zone. The solution is specified in terms of u.. and v... 1J 13 The actual allocation is therefore r.. + u.. + v... 1J 1J 13 This example is a small version of an actual problem that exists for university planners. At The University of Michigan in Ann Arbor, three campuses are North, Central, and Athletic. Nine site uses are organic gardening, crafts centers, day-care centers, married-student housing, highrise apartments, classrooms and office space, parking, single-student apartments, and industrial research. Goals have been specified for each use type (in thousands of square feet of land surface).

REFERENCES Hall, William K.; McWhorter, Archer; and Spivey, W. Allen, "Optimization Programs at The University of Michigan," Ann Arbor: Graduate School of Business Administration, The University of Michigan, 1971. IBM, "An Introduction to Modelling Using Mixed Integer Programming," IBM General Information Manual GE 19-5043-0, 1st ed., International Business Machines Corp., 1972. Spivey, W. Allen, "Optimization in Complex Management Systems," Research Working Paper 18, Ann Arbor: Bureau of Business Research, Graduate School of Business Administration, The University of Michigan, 1970., and Thrall, Robert M., "Linear Optimization," New York: Holt, Rinehart, and Winston, Inc., 1970. Steinitz, Carl, and Rogerts, Peter, "A Systems Analysis Model of Urbanization and Change: An Experiment in Interdisciplinary Education," Cambridge, Mass.: MIT Press, 1970.